DSA Unbounded Knapsack

The problem

Unbounded Knapsack packs copies of items into a bag with a weight limit to gain the most total value. Any item may repeat as long as the total weight still fits.

Each item has a weight and a value, and the supply of copies never runs out. The answer is the largest total value within the capacity, with the copy counts that earn it.

items = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5)]
cases = [(5, 7), (7, 10), (10, 15), (0, 0)]
for capacity, expected in cases:
    print("items:", items)
    print("capacity", capacity, "best value:", expected)

Capacity 10 is the case the 0/1 form cannot match. Five ropes weigh exactly 10 and give value 15. Taking each item at most once gives only 12 in the same bag.

Intuition: the once-each answer leaves value behind

The first idea reuses the 0/1 solution and takes each item at most once. It is a correct answer to a different problem. It refuses the copies that this problem allows.

items = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5)]
capacity = 10
best = 0
for mask in range(2 ** len(items)):
    group = [items[i] for i in range(len(items)) if mask & (1 << i)]
    weight = sum(item[1] for item in group)
    value = sum(item[2] for item in group)
    if weight <= capacity and value > best:
        best = value
print("best with each item once:", best)
print("five ropes value:", 5 * 3, "weight:", 5 * 2)

The gap of 3 comes from repetition alone. No new item types appear. The method must let a packed item stay available for the rest of the bag.

Brute force: count the copies of each item

The brute force tries every copy count for every item. At capacity 7 the rope can appear 0 to 3 times and the lamp 0 to 2 times. Each pair of counts is one candidate load, weighed and priced in full.

capacity = 7
checked = 0
best = 0
best_counts = (0, 0)
for ropes in range(capacity // 2 + 1):
    for lamps in range(capacity // 3 + 1):
        checked += 1
        weight = ropes * 2 + lamps * 3
        value = ropes * 3 + lamps * 4
        if weight <= capacity and value > best:
            best = value
            best_counts = (ropes, lamps)
print("loads checked:", checked)
print("best value:", best)
print("ropes, lamps:", best_counts)

Two item types already give 12 candidate loads. Each added type multiplies the ranges together. Each added unit of capacity stretches every range.

The optimal solution: best value at each capacity, scanning upward

The state is best(c), the most value that fits within capacity c. That one sentence is the whole method.

The table fills capacities upward, from small to large. A cell reads smaller capacities that this same pass has already finished. An item used at a smaller capacity is therefore still available at a larger one, and copies appear on their own.

def unbounded(items, capacity):
    dp = [0] * (capacity + 1)
    pick = [-1] * (capacity + 1)
    for c in range(1, capacity + 1):
        for idx, (name, weight, value) in enumerate(items):
            if weight <= c and dp[c - weight] + value > dp[c]:
                dp[c] = dp[c - weight] + value
                pick[c] = idx
    counts = []
    c = capacity
    tally = {}
    while c > 0 and pick[c] != -1:
        name, weight, value = items[pick[c]]
        tally[name] = tally.get(name, 0) + 1
        c -= weight
    for name, weight, value in items:
        if name in tally:
            counts.append((name, tally[name]))
    return dp[capacity], counts

items = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5)]
cases = [(5, 7), (7, 10), (10, 15), (0, 0)]
for capacity, expected in cases:
    best, counts = unbounded(items, capacity)
    print("capacity", capacity, "-> best", best, "expected:", expected, "match:", best == expected, "copies:", counts)

All four capacities match. The recovered copy counts show exactly which copies earn each value. Capacity 10 is earned by the rope alone, five times over.

Walkthrough: filling the table up to capacity 7

The walk fills one capacity at a time. Each line prints the whole table after that capacity is finished. The index of each entry is its capacity.

items = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5)]
capacity = 7
dp = [0] * (capacity + 1)
for c in range(1, capacity + 1):
    for name, weight, value in items:
        if weight <= c:
            dp[c] = max(dp[c], dp[c - weight] + value)
    print("after capacity", c, ":", dp)
print("best at capacity 7:", dp[7])

The last cell holds 10. Tracing the picks backward gives two ropes and one lamp. Their weight is exactly 7 and their value is 10.

Complexity

Time is O(capacity times items). Each capacity cell tries every item once.

Space is O(capacity). One row holds the best value for each capacity, and one pick beside it.

items = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5)]
for capacity in [5, 10, 20]:
    dp = [0] * (capacity + 1)
    checks = 0
    for c in range(1, capacity + 1):
        for name, weight, value in items:
            checks += 1
            if weight <= c:
                dp[c] = max(dp[c], dp[c - weight] + value)
    print("capacity", capacity, "- item checks:", checks, " best:", dp[capacity])

The checks grow as a plain product. Doubling the capacity doubles the work. No factor from the copy counts ever appears, because the upward scan creates the copies inside the same cells.

Edge cases and pitfalls

Capacity zero and an empty item list both answer 0. An item heavier than the capacity is never picked. Leftover space is allowed, because the limit is a maximum, not an exact fill.

def unbounded(items, capacity):
    dp = [0] * (capacity + 1)
    pick = [-1] * (capacity + 1)
    for c in range(1, capacity + 1):
        for idx, (name, weight, value) in enumerate(items):
            if weight <= c and dp[c - weight] + value > dp[c]:
                dp[c] = dp[c - weight] + value
                pick[c] = idx
    counts = []
    c = capacity
    tally = {}
    while c > 0 and pick[c] != -1:
        name, weight, value = items[pick[c]]
        tally[name] = tally.get(name, 0) + 1
        c -= weight
    for name, weight, value in items:
        if name in tally:
            counts.append((name, tally[name]))
    return dp[capacity], counts

items = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5)]
print("no capacity:", unbounded(items, 0))
print("no items:", unbounded([], 5))
print("item too heavy:", unbounded([("boulder", 10, 100)], 5))
print("leftover space:", unbounded([("lamp", 4, 5)], 6))

Scanning the one row downward is the classic mix-up between the two knapsack forms. A downward scan reads cells from before this item's pass, so each item enters only once.

weight = 2
value = 3
down = [0] * 7
for c in range(6, weight - 1, -1):
    down[c] = max(down[c], down[c - weight] + value)
print("downward table:", down)
up = [0] * 7
for c in range(weight, 7):
    up[c] = max(up[c], up[c - weight] + value)
print("upward table:", up)

The downward table stops at value 3 for one rope. The upward table reaches 9 from three ropes. The scan direction alone decides whether copies exist.