Repair compressed dynamic-programming layer order

Understand the likely causes

• Storage compression removed the item dimension, but the loop order reads the current item layer instead of the previous one.
• Base-state initialization or predecessor retention no longer matches the stated exact/at-most and reuse contracts. A correct-looking table can solve a different problem.

Write the uncompressed state in words

For zero-one knapsack, define best[i,c] as the maximum value using only the first i items with total weight at most c. Taking item i must read best[i-1,c-weight], because that item has not yet been used in the source layer. Skipping reads best[i-1,c]. This sentence identifies the dependency before any optimization. If the problem instead permits unlimited copies or requires exact weight, rewrite the state and base cases first. Do not infer semantics from the direction of a loop left behind by a previous implementation.

Track which conceptual layer each read represents

A one-row implementation updates capacities downward so c-weight has not yet been overwritten for the current item. Upward iteration would allow the weight2 item to improve capacity2, then read that new value while updating capacity4 and use the same item again. The program compares a clear two-dimensional reference with the corrected descending row. Both are valid local calculations; agreement helps expose compression errors without treating the faulty ascending version as a runnable teaching solution. This diagnostic keeps the simple item and capacity small enough to inspect by hand.

def table_reference(items, capacity):
    previous = [0] * (capacity + 1)
    for weight, value in items:
        current = previous[:]
        for c in range(weight, capacity + 1):
            current[c] = max(previous[c], previous[c - weight] + value)
        previous = current
    return previous[capacity]

def compressed(items, capacity):
    best = [0] * (capacity + 1)
    for weight, value in items:
        for c in range(capacity, weight - 1, -1):
            best[c] = max(best[c], best[c - weight] + value)
    return best[capacity]

fixture = [(2, 3)]
print(table_reference(fixture, 4))
print(compressed(fixture, 4))

3
3

Check initialization and reconstruction as separate contracts

Zero initialization is valid for an at-most-capacity maximum with an allowed empty selection. For exact weight, unreachable positive capacities need a separate sentinel; otherwise the table can fabricate a solution by extending an impossible state. Minimum-cost problems similarly need infinity except at valid bases. Reconstruction adds another obligation: predecessors must identify the transition and item layer that established each value. A compressed row can overwrite that history even when the final objective remains correct. Preserve appropriate layers, recompute choices deliberately, or use a proved reconstruction method rather than following whatever parent value remains.

Enumerate independent subsets on tiny fixtures

Generate small item lists and enumerate every subset, summing each subset’s weight and value directly. Compare the best feasible value with both implementations. Include one item, duplicate-valued but distinct items, capacity zero, an item heavier than capacity, and optional negative-valued items when the empty selection is allowed. For any reconstructed result, verify each input occurrence is used at most once, total weight is feasible, and value equals the objective. Tests using only unique values can miss accidental occurrence reuse. Keep all enumeration bounded; no large combinatorial benchmark is required for this diagnosis.

Keep it from recurring

• Keep the state sentence, layer-read invariant, loop order, and initialization together in review. Retain the one-item reuse counterexample and validate predecessor chains separately from objective values.