Loading...
Loading...
Loading...
Sneha is flying home for Diwali with one cabin bag. The airline allows at most W kilograms in it. She has n items she would like to carry, such as sweets, gifts and books. Item i weighs w_i kilograms and has a value v_i that says how much it matters to her.
Each item is either packed whole or left behind, and she has only one of each. The total weight of the packed items must be at most W.
Print the largest total value she can pack.
Example 1
Input
4 7 3 40 4 50 2 30 5 70
Output
100
Pack the items of weight 2 and 5: total weight 7, total value 100.
Example 2
Input
3 10 6 60 5 45 5 45
Output
90
The two items of weight 5 give 90. The single item of weight 6 gives only 60.
Try the problem first. Open one hint at a time.
Think about the items one at a time. For each item there are only two choices: pack it or leave it.
Let best[cap] be the largest value using the items seen so far with a total weight of at most cap.
Packing item i with weight w and value v gives best[cap - w] + v, where best[cap - w] must not already use item i.
With a one-row table, go through cap from W down to w. Going downward means best[cap - w] still describes the earlier items only.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor