燃やす埋める

ProjectSelectionProblem、別名「燃やす埋める」

燃やして埋める前に

説明

この問題では?のマスを白か黒に塗ることができる…が、?のマスをどう塗ったかによって、上下左右のマスに対する制限が変わったりする。こんな感じで、「設定項目が沢山あって、それぞれに依存関係があって、得点を増やしたい」みたいな問題に「燃やす埋める」テクを使うことができる…

ProjectSelectionProblemの方が直感で理解しやすい、それはそう

制約を、辺の加え方で表現する

最大値を求める問題を、最小値を求める問題に変換する