https://www.slideshare.net/mobile/shindannin/project-selection-problem 燃やす埋める 最小カット 燃やす埋める??
- 複数の小問題があり、選択肢がある、選択によってコストが変わる
- 小問題の選択に依存関係がある
- 問題数が20くらいなら全探索で解ける
- 10000とかの時に最小カットに帰着して解ける →DPとはどう違うか?
『燃やす埋める』という概念はそろそろ消え去るべきだと思っています。なぜかというとProject Selectionの形そのものを覚えれば瞬殺だから http://tokoharuland.hateblo.jp/entry/2017/11/12/234636 http://tokoharuland.hateblo.jp/entry/2017/12/25/000003 Project Selection Problem