Bounded Knapsack

01-25-2026

Description

This version Knapsack is the middle-ground between 01 Knapsack and Unbounded Knapsack. In these types of problems, as you may have guessed, each item now has a count limit associated to it. These limits are not necessarily uniform across items.

From an implementation perspective, the introduction of an entire different set of states to keep track of makes solving these problems a little bit tricker. However, with the right approach, you can essentially boil bounded knapsack into 0/1 knapsack.

How To Identify

The key characteristics of bounded knapsack are obvious:

  1. Dynamic Programming
  2. Constraints
  3. Items
  4. Can use an item c[i] times. I.e. you are provided a list of limits per item.

General Template and Approach

The standard approach to these problems is to reduce them to something similar: 0/1 Knapsack. This is typically performed thru binary decomposition. For a given count c for an item i, you decompose c into a binary representation and weight different chunks of i. The high level idea is that you separate i into different chunks which act as their own items. For example: given c == 13 and an item i, we would create new items:

  • weight and value: i*1
  • weight and value: i*2
  • weight and value: i*4
  • weight and value: i*6

The template for programming this is:

python
items = []
for i in range(n):
    count = c[i]
    k = 1
    while k <= count:
        items.append((k * w[i], k * v[i]))
        count -= k
        k <<= 1
    if count > 0:
        items.append((count * w[i], count * v[i]))

Now all thats left is to run 0/1 Knapsack!

python
dp = [0] * (W + 1)

for weight, value in items:
    for cap in range(W, weight - 1, -1):
        dp[cap] = max(dp[cap], dp[cap - weight] + value)

Solved Problems