ナップサック問題
問.
$ n個の品物があり、ii 番目の品物のそれぞれ重さと価値が weight[i],value[i] となっている ($ i=0,1,...,n−1)。
これらの品物から重さの総和が $ W を超えないように選んだときの、価値の総和の最大値を求めよ
制約
1. $ 1 \leq n \leq 100
2. weight[i], value[i] は整数
3. $ 1 \leqweight[i], value[i]$ \leq 1000
4. $ 1 \leq W \leq 10000
解答
Links