Pack for the Hike
Piece of gear i weighs weights[i] and is worth values[i] to you on a hike. Your pack can carry a total weight of at most capacity.
Choose which gear to take, each piece at most once, and return the largest total worth that fits in the pack. Taking nothing is allowed and is worth 0.
Example 1
weights [3,4,5]
values [30,50,60]
capacity 8
returns 90
Take the gear weighing 3 and 5, worth 30 + 60 = 90. The two lightest pieces are worth only 80.
Example 2
weights [5,6]
values [10,12]
capacity 4
returns 0
Neither piece fits, so the pack stays empty.
Constraints
0 <= len(weights) <= 30len(values) == len(weights)1 <= weights[i] <= 1000 <= values[i] <= 10000 <= capacity <= 200
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.