You are packing a bag that can carry at most a fixed total weight cap. There are n items; item i has an integer weight w_i and an integer value v_i. Each item may be taken at most once (you either pack the whole item or leave it — no fractions).
Choose a subset of items whose combined weight does not exceed cap and whose combined value is as large as possible. Report that maximum total value.
Line 1: two integers n and cap.
The next n lines: each contains two integers w_i and v_i — the weight and value of item i.
A single integer: the maximum total value achievable without exceeding the capacity. If no item fits (for example when cap is 0), the answer is 0.
0.Four items, capacity 5
Input
4 5 1 1 2 6 3 10 5 16
Expected
16
Explanation
Taking the items of weight 2 and 3 gives weight 5 and value 6 + 10 = 16; the single weight-5 item also yields 16, and no selection beats it, so the answer is 16.
Heavy high-value item excluded
Input
3 4 4 20 3 8 2 9
Expected
20
Explanation
The weight-4 item alone has value 20, which already fills the bag exactly; combining the weight-3 and weight-2 items exceeds capacity, so the best value is 20.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →