Every item, once each, best value
Generalise "can this sum be reached?" to "what's the most value this capacity can hold?" About 13 minutes.
From "can I?" to "how much?"
Earlier you kept a checklist of which totals were possible. Here every weight limit gets a number instead of a tick: the most value you can pack into that much space.
Bring the items in one at a time. For each space size, you either leave the new item out (the best value stays the same) or take it (its value, plus the best you could fit in the space that's left). Keep the bigger.
Big spaces first, so nothing is packed twice
Just like the banknote checklist, go through the space sizes from the biggest down. That way, when you work out "take it", the smaller space you look at doesn't already include this same item.
With a 7 kg bag and items weighing 1, 3, 4 and 5 kg (worth 1, 4, 5 and 7), the best is 9: the 3 kg and 4 kg items together fill the bag exactly.
for c in range(10, 2, -1):
print(c) # 10, 9, ..., 3Each box is the most value that fits in that much space. With no items packed yet, every box is 0.
A new item weighs 5 kg and is worth 10. Without it, 8 kg of space is worth 12 at best, and 3 kg is worth 4. What's 8 kg of space worth now?
- A14
- B12
- C10
Show the answer
14. Take it: 10 for the item plus 4 for the 3 kg left over. 14 beats 12.
Knapsack, maximum value
You get weights and values for n items (weights[i] and values[i] describe item i), and a capacity. Choose a subset of items, each used at most once, whose total weight is at most capacity. Return the largest total value achievable.
weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7 → 9
0 ≤ n ≤ 1,000 · 1 ≤ weights[i] ≤ 1,000 · 0 ≤ values[i] ≤ 1,000 · 0 ≤ capacity ≤ 1,000