Hard
C-004c0/1 Knapsack
Problem
You can carry at most W kg. Each of n items has a weight and value. Maximize total value without exceeding W.
Input
Line 1: n W. Next n lines: weight value.
Output
Max achievable value.
Constraints
1 ≤ n ≤ 1000, 1 ≤ W ≤ 10000
Sample input
3 5 1 10 3 40 4 30
Sample output
50
Explanation
Pick items 1 and 2 (weight 4, value 50).
dpknapsack@Amazon@Flipkart
Visible test cases
in: 3 5 1 10 3 40 4 30
out: 50
Your solution — run it, use AI if stuck
c