012 - うっちーとうっちーのおかいもの
時間制限 1 秒 / メモリ制限 32 MB / 得点 5 / x 8 /
問題
うっちー(woody_1227)とうっちー(gousuper)は2人でお買い物にきました。
2人の所持金の合計は$M$円で、それを超えないようになるべく満足度の高い買い物をしたいと思っています。
そのお店には$N$個の商品があり、$i$番目の商品の値段は$Cost_i$円、その商品を買った時に増える満足度は$Value_i$です。
所持金の合計を超えないように買い物をしたときの満足度の合計の最大値を出力してください。
買い物前の満足度は$0$とします。
入力
$N$ $M$ $Cost_0$ $Value_0$ $Cost_1$ $Value_1$ $Cost_2$ $Value_2$ : $Cost_{N-1}$ $Value_{N-1}$
出力
問題文のとおり
制約
全ての入力において以下を満たす。
- $1 ≤ N ≤ 20$
- $1 ≤ M ≤ 10^{18}$
- $1 ≤ Cost_i ≤ 10^9$
- $-10^9 ≤ Value_i ≤ 10^9$
入出力例
入力例1
4 100 50 6 60 9 40 3 10 4
出力例1
131つ目、3つ目、4つ目の商品を買うと、満足度が最大になります。
入力例2
3 50 60 9 110 2 89 1227
出力例2
0お金が足りなくて何も買えないことも...
入力例3
5 114514 10 -810 20 -364364 30 -1210 40 -316 50 -1919
出力例3
0買うと不満になる可能性もあります。
返品はできないので買わないようにしましょう。
ACしていない方への内容の共有はご遠慮ください。
問題制作の裏側
実はこれ、DPの典型であるナップサック問題が元になってるんですよ。
制約上、この問題はDPで解けないけどどうすれば効率よく解けるか考えてみるとおもしろいかも。