Unlimited copies, one loop direction flips
Same table, same recurrence — but counting capacity upward lets an item be reused. About 12 minutes.
When the shop never runs out
Now you can take as many copies of each item as you like, like filling a van with boxes from a warehouse that never runs out.
The rule is exactly the same as before: leave it, or take it and add the best for the space left over. The only thing that changes is the order you fill in the space sizes, and that one change is what allows repeats.
Small spaces first, so an item can come back
Fill the space sizes from small to big. When you work out "take it" for a large space, the smaller space you look at was just filled in, and it might already contain this same item. Taking it again means a second copy, which is exactly what's allowed now.
With kinds weighing 1, 3 and 4 (worth 1, 4 and 5) and 7 kg of space, the best is 9, for example two 3 kg boxes and one 1 kg box.
for c in range(w, capacity + 1):
pass # forwards: items can repeatCapacity grows from 1 upward, trying every kind at each one. Capacity 1: nothing weighs 1 or less, so the best is 0.
One kind of box weighs 3 kg and is worth 4. The best for 3 kg of space is 4 (one box). With unlimited boxes, what's the best for 6 kg?
- A8
- B4
- C0
Show the answer
8. Take another box on top of the best for 3 kg: 4 + 4 = 8, two boxes.
Unbounded knapsack
You get weights and values for n kinds of item, and a capacity. You may take any number of copies of each kind (including zero), as long as the total weight is at most capacity. Return the largest total value achievable.
weights = [1, 3, 4], values = [1, 4, 5], capacity = 7 → 9
0 ≤ n ≤ 1,000 · 1 ≤ weights[i] ≤ 1,000 · 0 ≤ values[i] ≤ 1,000 · 0 ≤ capacity ≤ 1,000