Skills101
← All coding problems

0/1 Knapsack

easyDynamic Programming II+10 XPTime limit 2s

A trekker's bag can carry at most W kilograms. There are n items; item i weighs w kg and is worth v points. Each item can be taken at most once (you can't take half an item). Which items maximise the total worth without going over W? Print that maximum worth.

Input:

  • line 1: n W
  • next n lines: w v for each item

Output: the maximum total worth.

Constraints: 1 ≤ n ≤ 100, 1 ≤ W ≤ 10⁴, 1 ≤ w ≤ 10⁴, 0 ≤ v ≤ 10⁶.

Think about it: best[c] = the best worth using capacity c. For each item, update best[c] = max(best[c], best[c − w] + v) going from high c to low c, so the item is used at most once. O(n · W). Trying all 2ⁿ subsets is hopeless for n = 100.

Sample input 1

4 7
1 1
3 4
4 5
5 7

Sample output 1

9

Sample input 2

3 5
6 10
7 20
8 30

Sample output 2

0

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.