Bounded Knapsack Problem

Each item can be used up to k_i times. State often dp[i][w] = best value using first i item types with weight w; compress inner loop over copies or use monotone queue tricks for speed.

Why this shows up in the real world

Warehouse packing with per-SKU limits. Budget allocation where each project has a cap on funded slots.

Core idea (explained for students)

Triple loop for i, for w, for c in range(min(k, w//wt)) is the baseline; optimize with binary splitting items into powers of two copies to reuse 0/1 knapsack structure.

Try this in Python

def bounded_knapsack(weights: list[int], values: list[int], counts: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for wt, val, cnt in zip(weights, values, counts):
        for _ in range(cnt):
            for w in range(W, wt - 1, -1):
                dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]


print(bounded_knapsack([1, 2], [10, 20], [2, 1], 4))

Common mistakes

• Treating bounded as unbounded and allowing infinite copies.
• Wrong base when weight cannot reach exactly.

Key takeaways

• Binary decomposition of counts is a standard interview upgrade.
• Test with all weights unreachable except zero.