0/1 Knapsack (recursion)

Medium TimeO(2ⁿ) naive; O(n·capacity) memoised SpaceO(n) stack

Each item has a weight and a value, and the bag carries only so much in total. Return the greatest value that fits. An item is taken whole or left behind — never partially, and never twice — the total weight taken may not exceed the limit, and weights and values are not negative.

Examples

Example 1

Input
weights = [1, 3, 4, 5]values = [1, 4, 5, 7]capacity = 7i = 0
Output
9
Weights 3 and 4 fill the 7 exactly and are worth 4 + 5 = 9.

Example 2

Input
weights = [1, 3, 4, 5]values = [1, 4, 5, 7]capacity = 0i = 0
Output
0
The bag carries nothing, so no item fits and the value is 0.

The Code

function knapsack(weights, values, capacity, i) {
  if (i === weights.length || capacity === 0) return 0;
  if (weights[i] > capacity) {
    return knapsack(weights, values, capacity, i + 1);
  }
  const skip = knapsack(weights, values, capacity, i + 1);
  const take = values[i] + knapsack(weights, values, capacity - weights[i], i + 1);
  return Math.max(skip, take);
}
knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7, 0);
Done

The first 10 calls, of 22. This one does not fit on a page.

Step through knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7, 0) call by call

More like this

All dynamic programming examples (20) →