Field Backpack Loadout
Problem
A field engineer is packing for a site visit. Item i weighs weights[i] kilograms and is worth values[i] points of usefulness. The backpack holds at most capacity kilograms.
Each item is either packed once or left behind. Return the maximum total value of a loadout whose total weight does not exceed capacity.
Example 1
- Input:
- weights = [3, 4, 5, 2], values = [30, 50, 60, 15], capacity = 9
- Output:
- 110
Pack the 4 kg and 5 kg items: 9 kg in total, worth 50 + 60 = 110. Adding the 2 kg item to anything else never beats that.
Example 2
- Input:
- weights = [5, 6], values = [10, 12], capacity = 4
- Output:
- 0
Nothing fits, so the best loadout is empty.
Example 3
- Input:
- weights = [1, 2, 3], values = [6, 10, 12], capacity = 5
- Output:
- 22
Constraints
- 0 ≤ weights.length = values.length ≤ 100
- 1 ≤ weights[i] ≤ 1000
- 0 ≤ values[i] ≤ 1000
- 0 ≤ capacity ≤ 10^4
Hint
Show the first hint
Think about the items one at a time: for each, you either take it or you do not.
Walkthrough
How to approach it
01Clarify before coding
- Can an item be packed more than once? No, each item is a single physical object: take it or leave it.
- Must the backpack be exactly full? No, total weight must be at most capacity.
- Can the list be empty or the capacity zero? Yes; the answer is then 0.
02Brute force
Try all 2^n subsets of items, sum the weight and value of each, and keep the best subset that fits.
Cost: O(2^n · n) time: with n = 100 that is about 10^32 subsets, hopeless.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.