236. What Fits in the Bag
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.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.