231. 0/1 Knapsack
MediumKnapsack
Each item has a weight and value and can be taken at most once. Print the maximum total value with total weight ≤ W.
Input format
Line 1: n W Next n lines: weight value
Output format
The maximum value.
Example 1
Input
3 50 10 60 20 100 30 120
Output
220
Example 2
Input
1 5 6 100
Output
0
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…