Knapsack 1
题意翻译
$n$ 个物品,选取其中若干个物品,使得对选取的这些物品 $\sum w_i\leq W$ 的前提下最大化 $\sum v_i$。
其实就是背包问题。
题目描述
[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_d
$ N $ 個の品物があります。 品物には $ 1,\ 2,\ \ldots,\ N $ と番号が振られています。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N $) について、品物 $ i $ の重さは $ w_i $ で、価値は $ v_i $ です。
太郎君は、$ N $ 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は $ W $ であり、持ち帰る品物の重さの総和は $ W $ 以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ $ : $ $ w_N $ $ v_N $
输出格式
太郎君が持ち帰る品物の価値の総和の最大値を出力せよ。
输入输出样例
输入样例 #1
3 8
3 30
4 50
5 60
输出样例 #1
90
输入样例 #2
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
输出样例 #2
5000000000
输入样例 #3
6 15
6 5
5 6
6 4
6 6
3 5
7 2
输出样例 #3
17
说明
### 制約
- 入力はすべて整数である。
- $ 1\ \leq\ N\ \leq\ 100 $
- $ 1\ \leq\ W\ \leq\ 10^5 $
- $ 1\ \leq\ w_i\ \leq\ W $
- $ 1\ \leq\ v_i\ \leq\ 10^9 $
### Sample Explanation 1
品物 $ 1,\ 3 $ を選べばよいです。 すると、重さの総和は $ 3\ +\ 5\ =\ 8 $ となり、価値の総和は $ 30\ +\ 60\ =\ 90 $ となります。
### Sample Explanation 2
答えは 32-bit 整数型に収まらない場合があります。
### Sample Explanation 3
品物 $ 2,\ 4,\ 5 $ を選べばよいです。 すると、重さの総和は $ 5\ +\ 6\ +\ 3\ =\ 14 $ となり、価値の総和は $ 6\ +\ 6\ +\ 5\ =\ 17 $ となります。