FunctionRacerProblemsRace

Pack for the Hike

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems