10. 0/1 Knapsack
HardDynamic Programming
Given n items with weights and values and a bag of capacity W, choose a subset with total weight ≤ W and maximum total value. Each item can be taken at most once.
Input format
Line 1: n W Next n lines: weight value
Output format
The maximum total value.
Example 1
Input
3 50 10 60 20 100 30 120
Output
220
Example 2
Input
4 7 1 1 3 4 4 5 5 7
Output
9
Constraints
1 ≤ n ≤ 100 1 ≤ W ≤ 10⁴
Read input from standard input and print the answer to standard output. Your code is judged against 5 test cases, most of them hidden.
Loading the MyLoginn IDE…