Dynamic ProgrammingKnapsack
You have n items, each with a weight and a value, and a bag that can carry total weight W. Each item can be taken at most once. Find the maximum total value you can carry.
Input
Line 1: n and W. Line 2: the n weights. Line 3: the n values.
Output
Print the maximum total value.
Constraints
1 <= n <= 200 1 <= W <= 1000 1 <= weight <= 100 1 <= value <= 1000
Example 1
Input
3 4 1 3 4 15 20 30
Output
35
Take items 1 and 2 (weights 1 + 3) for a value of 35.