236. What Fits in the Bag
Challenge1000 ms256 MBSolved by 0%
n items, each with a weight and a value, and a bag that holds at most C
total weight. Each item may be taken at most once.
Print the largest total value that fits.
The recursion is the same in-or-out choice as counting subsets: for each item, either take it, which costs its weight and gains its value, or skip it. That explores 2^n possibilities.
The saving is that most of those choices reach the same situation. What matters after some decisions is only which item you are considering and how much capacity is left, not which particular items got you there.
Constraints - `1 ≤ n ≤ 100` - `0 ≤ C ≤ 1000` - `1 ≤ weight ≤ 1000` - `1 ≤ value ≤ 1000000`
Input
The first line contains two integers n and C.
The second line contains n weights.
The third line contains n values.
Output
Print one integer, the largest total value that fits within the capacity.
Input4 7
1 3 4 5
1 4 5 7
Output9
Noteis the standard example, taking the 3 and the 4
Input1 0
1
10
Output0
Notehas no capacity at all, so nothing can be taken
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution