DSA Knapsack Variants

The problem: bounded knapsack

Bounded knapsack packs a bag up to a weight capacity. Each kind of item has a weight, a value, and a limited number of copies. The bag may take any count of copies from zero up to that limit.

The answer is the largest total value that fits. The main case below uses three kinds of items at capacity 10.

cases = [
    ([(2, 5, 3), (3, 7, 2), (1, 2, 5)], 10, 24),
    ([(2, 5, 2)], 4, 10),
    ([(2, 5, 3), (3, 7, 2)], 0, 0),
    ([(5, 9, 2)], 4, 0),
]
for items, cap, expected in cases:
    print("items", items, "capacity", cap, "best value:", expected)

Read the rows as weight, value, copies. The third row has capacity zero, so nothing fits. The fourth row holds only an item heavier than the bag.

Intuition: pack by best value per weight

The first idea ranks items by value per unit of weight and fills the bag greedily from the top of that ranking. The ranking is easy to compute. It can strand space that a slightly worse item would have used well.

items = [(3, 7, 1), (2, 4, 3)]
cap = 6
ranked = sorted(items, key=lambda it: it[1] / it[0], reverse=True)
total_w = 0
total_v = 0
for w, v, copies in ranked:
    take = min(copies, (cap - total_w) // w)
    total_w += take * w
    total_v += take * v
    print("take", take, "of weight", w, "value", v)
print("greedy value:", total_v, "weight used:", total_w, "of", cap)
print("best value is:", 12)

The greedy fill takes the dense item and one lighter item, then wastes one unit of space. Three light items fill the bag exactly and score more. A table that tries real combinations avoids the trap.

Brute force: expand every copy into its own item

The brute force rewrites each kind as separate single items, one per copy. A plain zero-one knapsack then runs over the expanded list. A counter records how many item passes the table makes.

A zero-one knapsack is the base problem where each item is taken or left once. Its one-row table updates capacities from high to low, so one item never feeds itself twice in one pass.

def knapsack_expanded(items, cap):
    table = [0] * (cap + 1)
    fills = 0
    for weight, value, copies in items:
        for _ in range(copies):
            fills += 1
            for w in range(cap, weight - 1, -1):
                table[w] = max(table[w], table[w - weight] + value)
    return table[cap], fills

items = [(2, 5, 3), (3, 7, 2), (1, 2, 5)]
best, fills = knapsack_expanded(items, 10)
print("expanded best:", best, "item passes:", fills)

The answer is right. The pass count is the total copy count, so a kind with a thousand copies costs a thousand passes. The copy count, not the bag, sets the price.

The optimal solution: split copies into bundles

Binary splitting rewrites a copy count as bundles whose sizes are powers of two plus one remainder bundle, and each bundle then acts as a single zero-one item. That rewrite is the whole method.

Bundle sizes combine to form every count from zero up to the limit, so no packing is lost. Thirteen copies split into bundles of 1, 2, 4 and 6, and four bundles replace thirteen items.

def split_copies(k):
    bundles = []
    power = 1
    while k > 0:
        take = min(power, k)
        bundles.append(take)
        k -= take
        power *= 2
    return bundles

def knapsack_split(items, cap):
    table = [0] * (cap + 1)
    fills = 0
    for weight, value, copies in items:
        for b in split_copies(copies):
            fills += 1
            bw, bv = b * weight, b * value
            for w in range(cap, bw - 1, -1):
                table[w] = max(table[w], table[w - bw] + bv)
    return table[cap], fills

cases = [
    ([(2, 5, 3), (3, 7, 2), (1, 2, 5)], 10, 24),
    ([(2, 5, 2)], 4, 10),
    ([(2, 5, 3), (3, 7, 2)], 0, 0),
    ([(5, 9, 2)], 4, 0),
]
for items, cap, expected in cases:
    best, fills = knapsack_split(items, cap)
    print("capacity", cap, "-> best", best, "expected:", expected, "match:", best == expected, "bundle passes:", fills)

Every case matches the expanded method. The main case drops from ten item passes to seven bundle passes, and the gap widens fast as copy counts grow.

Walkthrough: splitting 13 copies, then packing the main case

The walk shows the split first. It then prints the table row for the main case after each kind of item has been packed.

def split_copies(k):
    bundles = []
    power = 1
    while k > 0:
        take = min(power, k)
        bundles.append(take)
        k -= take
        power *= 2
    return bundles

print("13 copies split into:", split_copies(13))
print("5 copies split into:", split_copies(5))
print("1 copy splits into:", split_copies(1))

items = [(2, 5, 3), (3, 7, 2), (1, 2, 5)]
cap = 10
table = [0] * (cap + 1)
for weight, value, copies in items:
    for b in split_copies(copies):
        bw, bv = b * weight, b * value
        for w in range(cap, bw - 1, -1):
            table[w] = max(table[w], table[w - bw] + bv)
    print("after item weight", weight, "value", value, "copies", copies, "row:", table)
print("best at capacity 10:", table[cap])

The last row climbs to 24 at capacity 10. Each row only rises, because packing more kinds can never hurt the best value at any capacity.

Complexity

The expanded method makes one pass per copy, so its time is O(total copies times capacity). The split method makes one pass per bundle, about log of the copy count per kind, so its time is O(kinds times log copies times capacity), and both methods use O(capacity) space for the one-row table.

def split_count(k):
    count = 0
    power = 1
    while k > 0:
        take = min(power, k)
        k -= take
        power *= 2
        count += 1
    return count

for copies in [10, 100, 1000]:
    print("copies", copies, "- expanded passes:", copies, " split passes:", split_count(copies))

A thousand copies cost a thousand expanded passes and ten split passes. The saving is the logarithm, printed, not asserted.

A second limit beside weight, such as a volume limit, adds one axis to the table. A weight axis of 6 cells and a volume axis of 5 cells give a grid of 30 cells, and each item pass fills the whole grid.

Edge cases and pitfalls

Zero copies contribute no bundles. Capacity zero answers zero. An item heavier than the bag is skipped by the descending loop on its own, since no capacity reaches its weight.

The classic pitfall drops the remainder bundle. Splitting 13 copies into only 1, 2 and 4 reaches at most 7 copies, and counts from 8 to 13 silently vanish. The remainder bundle of 6 in the walkthrough is what covers them.

def split_copies(k):
    bundles = []
    power = 1
    while k > 0:
        take = min(power, k)
        bundles.append(take)
        k -= take
        power *= 2
    return bundles

def knapsack_split(items, cap):
    table = [0] * (cap + 1)
    for weight, value, copies in items:
        for b in split_copies(copies):
            bw, bv = b * weight, b * value
            for w in range(cap, bw - 1, -1):
                table[w] = max(table[w], table[w - bw] + bv)
    return table[cap]

print("zero copies:", split_copies(0), knapsack_split([(2, 5, 0)], 10))
print("capacity zero:", knapsack_split([(2, 5, 3)], 0))
print("too heavy:", knapsack_split([(9, 50, 2)], 4))
print("bundles of 13 sum to:", sum(split_copies(13)))
print("reachable counts from bundles of 13:")
bundles = split_copies(13)
reachable = set()
for mask in range(1 << len(bundles)):
    s = 0
    for i in range(len(bundles)):
        if mask >> i & 1:
            s += bundles[i]
    reachable.add(s)
print(sorted(reachable))

The reachable row lists every count from 0 to 13 with no gap. That full coverage is the proof the split loses nothing.