The Knapsack Problem

The Problem-Solving Patterns topic measured eight patterns together with their preconditions. There, the problem’s name was the pattern’s name: two pointers, sliding window, grid traversal. This topic turns that around. It takes up six classical problems whose names come not from a pattern but from the problem itself, and in each one the question is: which pattern does this problem fit, and where does the pattern it seems to fit break down.

The first problem is the knapsack, and it has two faces. Items with weight and value, and a bag of limited capacity. In the fractional variant, part of an item can be taken; in the 0/1 variant, an item is taken whole or not at all. This one-word difference is enough to make the same greedy order match the oracle on every input in one variant and be wrong in the other.

• CP1. The shared definition’s generator and input pool are used unchanged: seed 20260218, second pool 20260219, 40 sequences with 12 values each.
• CP2. In every sequence, the first six values are weight, the last six are value. Both are made absolute and incremented by one, so weight and value stay between 1 and 21.
• CP3. Capacity is half the total weight, rounded down. It is derived from the input, not chosen by hand; otherwise the desired result could be produced just by picking the capacity.
• CP4. The oracle is brute force in both variants: every fill order in the fractional variant, all 64 subsets in the 0/1 variant. The oracle is expensive, and it stays that way.
• CP5. The measure is steps; time is not measured. A step is the one unit the oracle and the pattern can be compared in.
• CP6. The split-input count is out of 40. Per the shared definition’s Section 5 resolution, a difference below 3 counts as unmeasured.
• CP7. The greedy order is the same in both variants: decreasing value-to-weight ratio. The only thing that changes is whether an item can be split.
• CP8. The dynamic programming procedure was built in the Algorithm Design Approaches topic; it is not rebuilt, only compared against the oracle.
• CP9. Capacity is also swept as a setting. A split count measured at a single capacity and generalized is a consequence of the chosen setting, and it is written that way.

The Fractional Variant and Its Oracle

In the fractional variant, any desired fraction of an item can be taken. The intuition is straightforward: start with the item giving the most value per unit weight, continue in order until the bag is full, and take a fraction of the last item equal to the remaining space.

This intuition is not claimed to be correct — it is tested. The oracle tries every fill order of the six items and keeps the best. A fill order fills the bag in sequence; whichever order is taken, the value obtained cannot exceed the best possible value, and the order giving the best value is among these 720 orders. So the oracle is genuinely an upper bound.

from itertools import permutations

SEED = 20260218


def generator(seed):
    d = seed

    def next_val(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_val


def item_pool(seed=SEED, n=40, length=12):
    r = generator(seed)
    return [{"no": i + 1, "values": [r(30) - 9 for _ in range(length)]}
            for i in range(n)]


def items(values):
    """Six items from the shared definition's 12 values: weight first six, value last six."""
    return [(abs(values[i]) + 1, abs(values[i + 6]) + 1) for i in range(6)]


class Counter:
    def __init__(self):
        self.steps = 0

    def count(self):
        self.steps += 1


def oracle_fractional(its, capacity, c):
    """Every fill order is tried, the best is kept."""
    best = 0.0
    for p in permutations(range(len(its))):
        remaining, v = capacity, 0.0
        for i in p:
            c.count()
            w, val = its[i]
            if w <= remaining:
                remaining, v = remaining - w, v + val
            else:
                v += val * remaining / w
                break
        best = max(best, v)
    return round(best, 4)


def pattern_fractional(its, capacity, c):
    """PRECONDITION: items must be divisible. Greedy by value-to-weight ratio."""
    remaining, v = capacity, 0.0
    for w, val in sorted(its, key=lambda t: -t[1] / t[0]):
        c.count()
        if w <= remaining:
            remaining, v = remaining - w, v + val
        else:
            v += val * remaining / w
            break
    return round(v, 4)


split, pk, ok = 0, 0, 0
for k in item_pool():
    its = items(k["values"])
    capacity = sum(w for w, _ in its) // 2
    c1, c2 = Counter(), Counter()
    if pattern_fractional(its, capacity, c1) != oracle_fractional(its, capacity, c2):
        split += 1
    pk, ok = pk + c1.steps, ok + c2.steps
print("first example (weight, value):", items(item_pool()[0]["values"]))
print("fractional | inputs 40 | split", split, "| pattern steps", pk,
      "| oracle steps", ok, "| ratio", round(ok / pk, 1))

first example (weight, value): [(9, 5), (6, 2), (3, 17), (2, 18), (3, 7), (6, 2)]
fractional | inputs 40 | split 0 | pattern steps 174 | oracle steps 100800 | ratio 579.3

Three numbers sit side by side: the oracle at 100,800 steps, the pattern at 174 steps, 0 split inputs. The pattern spends 579.3 times fewer steps and matches the oracle on 40 of 40 inputs.

The reason greedy never goes wrong in the fractional variant is that the freedom to take a fraction allows an exchange. If a unit of weight in the bag belongs to a low-ratio item, removing that unit and putting in a unit from a high-ratio item instead never lowers the value. Because this exchange argument always holds, no solution that deviates from ratio order can beat ratio order. The precondition is exactly this: a unit of weight must be exchangeable.

The Same Order, an Item That Cannot Be Split

In the 0/1 variant, this exchange disappears. Removing a unit of weight requires removing the item’s whole weight, and the replacement item comes in whole too. The greedy order does not change, and the code is almost identical, but the precondition is no longer there.

SEED = 20260218


def generator(seed):
    d = seed

    def next_val(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_val


def item_pool(seed=SEED, n=40):
    """The shared definition's pool: 40 sequences x 12 values, six items per sequence."""
    r = generator(seed)
    pool = []
    for i in range(n):
        z = [r(30) - 9 for _ in range(12)]
        pool.append((i + 1, [(abs(z[j]) + 1, abs(z[j + 6]) + 1) for j in range(6)]))
    return pool


class Counter:
    def __init__(self):
        self.steps = 0

    def count(self):
        self.steps += 1


def oracle_01(its, capacity, c):
    """All 64 subsets of the six items are tried."""
    best = 0
    for mask in range(1 << len(its)):
        w = v = 0
        for i, (wi, vi) in enumerate(its):
            c.count()
            if mask >> i & 1:
                w, v = w + wi, v + vi
        if w <= capacity and v > best:
            best = v
    return best


def pattern_01(its, capacity, c):
    """Same greedy order, but items cannot be split."""
    remaining, v = capacity, 0
    for w, val in sorted(its, key=lambda t: -t[1] / t[0]):
        c.count()
        if w <= remaining:
            remaining, v = remaining - w, v + val
    return v


def dp_01(its, capacity, c):
    best = [0] * (capacity + 1)
    for w, val in its:
        for cap in range(capacity, w - 1, -1):
            c.count()
            best[cap] = max(best[cap], best[cap - w] + val)
    return best[capacity]


def measure(solver, seed):
    split, pk, ok, loss = [], 0, 0, 0
    for no, its in item_pool(seed):
        capacity = sum(w for w, _ in its) // 2
        c1, c2 = Counter(), Counter()
        a, b = solver(its, capacity, c1), oracle_01(its, capacity, c2)
        pk, ok = pk + c1.steps, ok + c2.steps
        if a != b:
            split.append(no)
            loss = max(loss, b - a)
    return split, pk, ok, loss


for name, solver, seed in (("greedy 20260218", pattern_01, 20260218),
                            ("greedy 20260219", pattern_01, 20260219),
                            ("dynamic 20260218", dp_01, 20260218)):
    sp, pk, ok, f = measure(solver, seed)
    print(name, "| split", len(sp), "/40", sp[:6], "| pattern steps", pk,
          "| oracle steps", ok, "| worst loss", f)

greedy 20260218 | split 5 /40 [4, 21, 22, 32, 40] | pattern steps 240 | oracle steps 15360 | worst loss 7
greedy 20260219 | split 6 /40 [8, 11, 20, 28, 36, 39] | pattern steps 240 | oracle steps 15360 | worst loss 3
dynamic 20260218 | split 0 /40 [] | pattern steps 4544 | oracle steps 15360 | worst loss 0

Reading the Split Inputs

In 0/1, greedy splits from the oracle on 5 of 40 inputs. The split ratio is 0.1250, above the resolution limit (3 inputs), so it counts as measured. The numbers of the inputs it splits on are known: 4, 21, 22, 32, and 40. The worst loss is 7 value units — seven units short of the best value the bag could carry.

This loss cannot be noticed by looking at the output. Greedy still returns a number, still stays within capacity, still produces a valid selection. Being valid does not mean being optimal, and only the oracle can reveal the difference. There is no way to look at the pattern’s answer alone and say it is wrong.

The second input pool is mandatory and is applied here too: with seed 20260219, the split count is 6, ratio 0.1500. The difference between five and six is below the resolution, but both ratios sit at the same order of magnitude. The result does not depend on the pool: in the 0/1 variant, greedy is wrong on roughly one input in seven.

Inside One Split Input

The split-input count is, by itself, just a number; it does not show what breaks. Opening up input 4 and placing the two selections side by side makes the mechanism visible. The same block also sweeps capacity as a setting.

SEED = 20260218


def generator(seed):
    d = seed

    def next_val(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_val


def item_pool(seed=SEED, n=40):
    r = generator(seed)
    pool = []
    for i in range(n):
        z = [r(30) - 9 for _ in range(12)]
        pool.append((i + 1, [(abs(z[j]) + 1, abs(z[j + 6]) + 1) for j in range(6)]))
    return pool


def oracle_01(its, capacity):
    best, choice = 0, ()
    for mask in range(1 << len(its)):
        w = v = 0
        for i, (wi, vi) in enumerate(its):
            if mask >> i & 1:
                w, v = w + wi, v + vi
        if w <= capacity and v > best:
            best, choice = v, tuple(i for i in range(len(its)) if mask >> i & 1)
    return best, choice


def pattern_01(its, capacity):
    remaining, v, choice = capacity, 0, []
    for i in sorted(range(len(its)), key=lambda j: -its[j][1] / its[j][0]):
        w, val = its[i]
        if w <= remaining:
            remaining, v = remaining - w, v + val
            choice.append(i)
    return v, tuple(sorted(choice))


its = dict(item_pool())[4]
capacity = sum(w for w, _ in its) // 2
print("input 4 |", its, "| capacity", capacity)
print("  greedy:", pattern_01(its, capacity), " oracle:", oracle_01(its, capacity))
print("capacity share -> split inputs (out of 40)")
for share in (2, 3, 4, 5, 6):
    split = sum(1 for _, e in item_pool()
                if pattern_01(e, sum(w for w, _ in e) * share // 8)[0]
                != oracle_01(e, sum(w for w, _ in e) * share // 8)[0])
    print(f"  {share}/8 -> {split}")

input 4 | [(5, 21), (6, 8), (9, 5), (2, 4), (19, 13), (18, 16)] | capacity 29
  greedy: (38, (0, 1, 2, 3))  oracle: (45, (0, 1, 5))
capacity share -> split inputs (out of 40)
  2/8 -> 3
  3/8 -> 13
  4/8 -> 5
  5/8 -> 12
  6/8 -> 8

Greedy takes four items and collects 38 value; the weight it uses is 22, leaving 7 units of empty space. The oracle takes three items, fills the capacity exactly, and collects 45 value. The source of the difference is that greedy takes the small, high-ratio items early and, as a result, leaves no room for the sixth item, which has a low ratio but is large. The sixth item’s ratio, 0.889, ranks fourth on the list, but it carries 16 value on its own. Greedy can never see it, because it builds its order by ratio alone and never looks back.

The capacity sweep gives a second, more unsettling result. The split count does not change regularly with capacity: 3 at two-eighths of the total weight, 13 at three-eighths, 5 at four-eighths, 12 at five-eighths, 8 at six-eighths. The pattern’s wrong-answer count is not a constant; it is a function of the setting. If the measurement had been taken at a single capacity and generalized, the 3 at the two-eighths setting would have given the impression that greedy is almost always right; the 13 at the three-eighths setting would say the exact opposite. Unless the setting the measurement was taken at is written down, the number cannot be read.

The Cost of Dynamic Programming

The third row shows dynamic programming: matches the oracle on 40 of 40 inputs, at 4544 steps. The oracle spends 15,360 steps, so the correct answer can be obtained with roughly a third of brute force’s steps. But compared with greedy’s 240 steps, it is 18.9 times more expensive.

These three rows are exactly what the course’s reading of measurement is about. Greedy is cheap and wrong; dynamic programming is expensive and correct; the oracle is the most expensive, and its correctness is known by definition. The choice between them is not a speed preference; it is the question of how many inputs a wrong answer is acceptable on.

It should be noted that dynamic programming’s step count grows with capacity. Here capacities are small, because weights fall between 1 and 21. If weights were multiplied by a thousand with the item count unchanged, dynamic programming’s steps would also multiply by a thousand; brute force’s steps, by contrast, would not change at all, since it only looks at the number of subsets. Which procedure is expensive depends on which dimension of the input grows.

Summary

• The knapsack’s two variants share the same greedy order; the one point where they differ is whether an item can be split, and that single point changes the answer.
• In the fractional variant, greedy matches the oracle on 40 of 40 inputs in 174 steps; the oracle does the same work in 100,800 steps.
• In the 0/1 variant, the same order splits from the oracle on 5 of 40 inputs, with a worst loss of 7 value units; on the second pool, the split count is 6, at the same order of magnitude.
• The answer greedy produces is always valid; being valid does not mean being optimal, and only the oracle reveals the difference.
• When capacity is swept as a setting, the split count moves between 3 and 13; the pattern’s wrong-answer count is not a constant, it is a function of the setting.
• Dynamic programming gives a correct answer on 40/40 in 4544 steps: 3.4 times cheaper than the oracle, 18.9 times more expensive than greedy.

Next Step

In the knapsack, the brute-force oracle scanned 64 subsets, and that scan stayed small. The next lesson takes up the travelling salesman problem; there, the number of candidate solutions is not subsets but orderings, and going from six cities to ten makes the search space explode in a way that can be shown numerically. The question will be: once the oracle grows too large to run at all, how is an approximate solution’s percentage deviation from the oracle measured.