Unbounded Knapsack

Like 0/1 knapsack, but each item can be used any number of times. A single 1-D array suffices: dp[c] tries every item at every capacity, allowing the same item to contribute again from a smaller remaining capacity.

Category: Dynamic Programming
Time complexity: O(n·capacity)
Space complexity: O(capacity)

Pseudocode

dp[0] = 0
for c in 1..capacity
  dp[c] = max over items of
    value + dp[c − weight] (if it fits)

Reference implementation

dp = [0] * (cap + 1)
for c in range(1, cap + 1):
    for w, v in items:
        if w &lt;= c:
            dp[c] = max(dp[c], dp[c-w] + v)

Open the interactive Unbounded Knapsack visualisation →