The 0/1 Knapsack

Difficulty: 1600 3000 ms 128 MB

dp

Each item has a weight and a value and can be taken at most once. Maximize the total value within capacity W.

Input: the first line has N and W; each of the next N lines has w_i and v_i.

Output: the maximum total value.

Constraints:

• 1 ≤ N ≤ 100
• 1 ≤ W ≤ 1000
• 1 ≤ w_i ≤ 1000
• 0 ≤ v_i ≤ 10⁴

Sample Tests

3 8
3 30
4 50
5 60

90

1 1
2 100

0

Read the Editorial