ABC060 D - Simple Knapsack
解法
ナップサックと書いてあるのでとりあえずDPを考えます。
をすべての重量から引いていくと、どれも0~3のいずれかの重量に置き換えることができます。
この重さを利用して、次のようなDPを考えていきます。
番目までの荷物の中で、
個使用したときに、総重量が
となるような組み合わせの中で最大の価値
すると、次のような遷移になります。
左側が番目の荷物を用いる場合、右側が用いない場合です。
そして、最終的な答えがどこに格納されているかを考えます。
仮にすべての荷物の重量が0であった場合、 が使用できる荷物の個数になります。 これを
とします。
重量が0の個荷物を使うと決めた時、
の重さ分の荷物だけ入れることができます。
ということで、 (ただし、
)
が答えの候補となるので、まずその中での最大値を記録しておきます。
次に、荷物を個使用する時を考えます。すると、
だけ先ほどより多く重い荷物を入れることができるので、
(ただし、
)
が答えの候補となります。
これを繰り返していくと、
(ただし、
)
の中での最大値を求めれば、答えとなります。
