#AT1076. D - Simple Knapsack
D - Simple Knapsack
当前没有测试数据。
D - Simple Knapsack
Score : $400$ points
Problem Statement
You have $N$ items and a bag of strength $W$. The $i$-th item has a weight of $w_i$ and a value of $v_i$.
You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most $W$.
Your objective is to maximize the total value of the selected items.
Constraints
- $1 ≤ N ≤ 100$
- $1 ≤ W ≤ 10^9$
- $1 ≤ w_i ≤ 10^9$
- For each $i = 2,3,...,N$, $w_1 ≤ w_i ≤ w_1 + 3$.
- $1 ≤ v_i ≤ 10^7$
- $W$, each $w_i$ and $v_i$ are integers.
Input
Input is given from Standard Input in the following format:
:
Output
Print the maximum possible total value of the selected items.
4 6
2 1
3 4
4 10
3 4
11
The first and third items should be selected.
4 6
2 1
3 7
4 10
3 6
13
The second and fourth items should be selected.
4 10
1 100
1 100
1 100
1 100
400
You can take everything.
4 1
10 100
10 100
10 100
10 100
0
You can take nothing.