AT_dp_e Knapsack 2
题目描述
$N$ 个物品被编号为 $1, 2, \ldots, N$。对于 $1 \leq i \leq N$，物品 $i$ 的重量是 $w _ i$，价值是 $v _ i$。
太郎君决定从 $N$ 个物品中选择一些放入背包中带回家。背包的容量为 $W$，带回的物品的总重量不能超过 $W$。
请计算太郎君能带回的物品的最大总价值。
输入格式
无
输出格式
无
说明/提示
### 制約
- 入力はすべて整数である。
- $ 1\ \leq\ N\ \leq\ 100 $
- $ 1\ \leq\ W\ \leq\ 10^9 $
- $ 1\ \leq\ w_i\ \leq\ W $
- $ 1\ \leq\ v_i\ \leq\ 10^3 $
### Sample Explanation 1
品物 $ 1,\ 3 $ を選べばよいです。 すると、重さの総和は $ 3\ +\ 5\ =\ 8 $ となり、価値の総和は $ 30\ +\ 60\ =\ 90 $ となります。
### Sample Explanation 3
品物 $ 2,\ 4,\ 5 $ を選べばよいです。 すると、重さの総和は $ 5\ +\ 6\ +\ 3\ =\ 14 $ となり、価値の総和は $ 6\ +\ 6\ +\ 5\ =\ 17 $ となります。