0/1 Knapsack

The 0/1 knapsack problem asks you to pack the most valuable subset of items into a bag with a fixed weight limit, where each item is taken whole or left behind — never split, never taken twice (that is the "0/1"). Each item i has a weight weights[i] and a value values[i], given as two parallel arrays. You return the maximum total value you can carry without the combined weight exceeding capacity. It is the textbook example of dynamic programming — see Knapsack problem for background.

Signature

knapsack01(weights, values, capacity)
  // weights[i], values[i]: the weight and value of item i (parallel arrays, same length)
  // capacity: the weight budget of the knapsack
  // -> number: the maximum total value that fits within the budget

Examples

// Items (weight, value): (1,1) (3,4) (4,5) (5,7); budget 7.
// Best pick: the (3,4) and (4,5) items — weight 3 + 4 = 7, value 4 + 5 = 9.
knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 7); // 9

// A bag with no room can hold nothing.
knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 0); // 0

// Every item fits at once, so the answer is the sum of all values.
knapsack01([1, 2, 3], [6, 10, 12], 6); // 28

Notes

• Parallel arrays — weights and values have the same length; weights[i] and values[i] describe the same item i.
• Each item is 0 or 1 — you take an item once or not at all. You cannot take a fraction of an item, and you cannot take the same item twice.
• Non-negative integers — assume every weight and the capacity are non-negative integers; values are non-negative too.
• Return the value, not the items — you return the maximum achievable total value, not which items were chosen.
• The limit is inclusive — a subset whose total weight equals capacity exactly is allowed.