ABC 060 D-Simple Knapsack
D - Simple Knapsack
ナップザック問題ときたら真っ先に重みでDPか価値でDPか半分全列挙かどれかだろうなあと思って制約を見たらも
も
も大きくてDPできず, さらには
の値も100と半分全列挙するには多すぎます. しかし, 特殊な制約
というものがあります. この制約からの取りうる数値は4種類しかないことがわかります. あとは入力をこの4種類に分類したあと価値順にソートします. 4種の重さからそれぞれいくつ取り出すかを全探索し, 価値の大きいものから貪欲に選び, その重みの和が
より小さければ, 最小値を更新します. すべてのパターンを探索すると答えが得られます.
