Loading
Loading
A hiker is packing for a long trail. Each piece of kit has a weight and a usefulness score, and there is only one of each. The rucksack can carry at most a fixed total weight.
Given weights and values (item i weighs weights[i] and is worth values[i]) and the capacity, return the highest total value of items that fit together within the capacity.
weights = [1, 3, 4, 5], values = [15, 50, 60, 90], capacity = 7after item 0: best[1..7] = 15only the light itemafter item 1: best[4..7] = 65items 0 and 1after item 2: best[7] = best[3] + 60 = 110items 1 and 2: weight 7after item 3: best[7] stays 1105 + 1 gives only 105110Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n × capacity) time · O(capacity) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
The items weighing 3 and 4 fit exactly, worth 50 + 60.
Example 2
Both items are heavier than the capacity.