<p><a href="https://www.slideshare.net/mobile/shindannin/project-selection-problem">https://www.slideshare.net/mobile/shindannin/project-selection-problem</a>
<a href="/ja/%E7%87%83%E3%82%84%E3%81%99%E5%9F%8B%E3%82%81%E3%82%8B">燃やす埋める</a>　<a href="/ja/%E6%9C%80%E5%B0%8F%E3%82%AB%E3%83%83%E3%83%88">最小カット</a>
燃やす埋める??</p>
<ul>
<li>複数の小問題があり、選択肢がある、選択によってコストが変わる</li>
<li>小問題の選択に依存関係がある</li>
<li>問題数が20くらいなら全探索で解ける<ul>
<li>10000とかの時に最小カットに帰着して解ける
→DPとはどう違うか？</li>
</ul>
</li>
</ul>
<blockquote>
<p>『燃やす埋める』という概念はそろそろ消え去るべきだと思っています。なぜかというとProject Selectionの形そのものを覚えれば瞬殺だから
<a href="http://tokoharuland.hateblo.jp/entry/2017/11/12/234636">http://tokoharuland.hateblo.jp/entry/2017/11/12/234636</a>
<a href="http://tokoharuland.hateblo.jp/entry/2017/12/25/000003">http://tokoharuland.hateblo.jp/entry/2017/12/25/000003</a>
<a href="/ja/Project%20Selection%20Problem">Project Selection Problem</a></p>
</blockquote>


最小カットを使って「燃やす埋める問題」を解く