[ABC060D] Simple Knapsack
题意翻译
你有 $N$ 个物品和容量为 $W$ 的背包,每个物品要么选要么不选,它们的体积为 $w_i$,价值为 $v_i$,求总体积至多为 $W$ 情况下能拿走物品价值的最大值。
**【数据范围】**
$1\le N \le 100$,$1\le W \le 10^9$,$1 \le w_i \le 10^9$
$w_1 \le w_i \le w_1+3 (i=2,3,\cdots N)$
$1 \le v_i \le 10^7$
$W,w_i,v_i$ 都是整数
翻译:[So_what](https://www.luogu.org/space/show?uid=68706)
题目描述
[problemUrl]: https://atcoder.jp/contests/abc060/tasks/arc073_b
あなたは $ N $ 個の物と、強度 $ W $ のバッグを持っています。 $ i $ 個目の物は、重さが $ w_i $ で価値が $ v_i $ です。
あなたは、物のうちいくつかを選び、バッグに入れます。 ただし、選んだ物の重さの和は $ W $ 以下でなくてはいけません。
あなたは、バッグに入れた物の価値の総和を最大化したいです。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ : $ w_N $ $ v_N $
输出格式
価値の総和の最大値を出力する。
输入输出样例
输入样例 #1
4 6
2 1
3 4
4 10
3 4
输出样例 #1
11
输入样例 #2
4 6
2 1
3 7
4 10
3 6
输出样例 #2
13
输入样例 #3
4 10
1 100
1 100
1 100
1 100
输出样例 #3
400
输入样例 #4
4 1
10 100
10 100
10 100
10 100
输出样例 #4
0
说明
### 制約
- $ 1\ ≦\ N\ ≦\ 100 $
- $ 1\ ≦\ W\ ≦\ 10^9 $
- $ 1\ ≦\ w_i\ ≦\ 10^9 $
- すべての $ i\ =\ 2,3,...,N $ について、$ w_1\ ≦\ w_i\ ≦\ w_1\ +\ 3 $
- $ 1\ ≦\ v_i\ ≦\ 10^7 $
- $ W,\ w_i,\ v_i $ はすべて整数である
### Sample Explanation 1
$ 1,\ 3 $ 個目の物を選ぶと良いです。
### Sample Explanation 2
$ 2,\ 4 $ 個目の物を選ぶと良いです。
### Sample Explanation 3
すべての物が選べます。
### Sample Explanation 4
$ 1 $ 個も物が選べません。