Unbounded Knapsack Algorithm Tutorial

Unbounded Knapsack

The Unbounded Knapsack problem is a classic DP problem where you maximize value given a weight capacity, with unlimited copies of each item available. It's also known as the "complete knapsack" problem.

You have $n$ item types with weights and values. You can use each type unlimited times. Your goal is to maximize value without exceeding capacity $W$.

You define $dp[w]$ as the maximum value achievable with capacity $w$. For each capacity, you try adding each item type and take the best result.

function unboundedKnapsack(W, weights, values, n):
    dp = array of size W + 1, initialized to 0

    for w from 1 to W:
        for i from 0 to n - 1:
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

Since items are unlimited, your $dp[w]$ depends on $dp[w - weight[i]]$ from the same row. You iterate forward through capacities, allowing the same item to be picked multiple times.

Applications: You use unbounded knapsack for coin change problems, rod cutting, and resource allocation where items can be reused.

Time complexity: $O(n \times W)$ because you check all $n$ items for each capacity up to $W$.

Space complexity: $O(W)$ for the $1$D DP array.