Unbounded knapsack

O(n·W)

Unbounded knapsack is the 0/1 knapsack with one rule relaxed: each item type may be used as many times as you like. The table dp[i][w] still holds the best value for capacity w using item types 1..i, but the "take" choice now reads the same row — dp[i][w − weight] + value — because after taking an item you may take it again. That single change (looking at the current row instead of the row above) turns the bounded problem into the unbounded one. It models making change with unlimited coins, cutting stock, and resource packing. Like its bounded cousin it fills in O(n·W).

Weights Values Capacity

DP table

Press ▶ to run

Edit the input and press Play

Loop

How it works

With no item types, every capacity holds value 0 — the base row.
For each item type and capacity, first copy the value that skips it (the row above).
If it fits, compare with its value plus the best for the leftover capacity — in the same row (reuse allowed).
Keep the larger; the bottom-right cell is the most valuable load.

Pseudocode

1unboundedKnapsack(weights, values, W):  # O(n·W)2  dp[0][w] ← 03  for each item i, capacity w in 1..W:4    best ← dp[i-1][w]                # skip this item type5    if w ≥ weight[i]:6      take ← dp[i][w-weight[i]] + value[i]   # reuse item i7      best ← max(best, take)8    dp[i][w] ← best9  return dp[n][W]