Quiz
https://yukicoder.me/problems/no/527
Submit
https://yukicoder.me/submissions/342051
解法
- 普通にナップサック問題を解く
- dp[i][j]
- i : i番目に着目
- j : 残りの容量
- その時の最大の価値
- dpテーブルを埋めた後、dp[0][各重み] == Vなる重みをリストアップ
- そのリストのmax, minが答え
- min==0のときは、1を返すようにする (容量は1以上と設定されている)
- max>100000のときは、infを返すようにする
その他
参考(メモ化再帰のナップサック)
http://dai1741.github.io/maximum-algo-2012/docs/dynamic-programming/