Unbounded Knapsack

The Idea

0/1 knapsack loops capacity backwards so an item cannot be reused. Unbounded knapsack loops forwards on purpose. Reading a cell this item has already improved is not a bug here — it is how the second and third copy get taken. Cutting stock, coin change and rod cutting are all this one recurrence.

Real-World Example

A print shop filling an 8-metre roll from three standard cut lengths. Stock is effectively unlimited, so the question is never "which cuts do I own" but "how many of each fit". The roll is priced metre by metre, reusing the best answer for the shorter roll underneath.

The Code

weights = [3, 4, 5]
values = [30, 50, 60]
cap = 8

best = [0] * (cap + 1)
for c in range(1, cap + 1):                       # forwards, unlike 0/1
    for w, v in zip(weights, values):
        if w <= c:
            best[c] = max(best[c], best[c - w] + v)   # item stays available

print(best)        # [0, 0, 0, 30, 50, 60, 60, 80, 100]
print(best[cap])   # 100 — two of the weight-4 item; 0/1 could only reach 90

best = [0] * 7
for c in range(1, 7):
  for w, v in [(2, 3), (5, 8)]:
      if w <= c:
          best[c] = max(best[c], best[c - w] + v)
print(best[6])