Running the One-Array Knapsack Loop Upwards

Running the inner loop of a one-array knapsack from small capacities up, instead of from the full capacity down, lets one item be packed several times, and the answer comes out too large. This card shows the symptom on three parcels, explains why the direction decides it, and gives the rule for each kind of knapsack.

The mistake raises no error. A courier's code reports £10 for a 6 kilo bag and parcels A (2 kilos, £3), B (3 kilos, £5) and C (4 kilos, £6), each available once. No real packing earns £10: the best is A and C, £9. The trigger is one changed line, the inner loop written as for c in range(w, W + 1) because counting up looks natural. A run printed the array after each parcel for both directions.

The upward row goes wrong with the very first parcel. At capacity 4 it computes best[4] from best[2] + 3, but best[2] was set to 3 a moment earlier, by A itself, so best[4] = 6 means A packed twice. Capacity 6 then reads best[4] and packs A three times, for 9. After B, capacity 6 reads best[3] + 5, and best[3] already holds B, so the final 10 is B packed twice. Downwards, every cell reads smaller capacities before they change, so each still holds the value without the current item, and each parcel is packed at most once.

The cost is a wrong total, and a plausible one, since £10 is close to £9 and passes any check that only asks whether the code runs. Tests on a single item catch it, because an item of weight 2 in a bag of 6 should give its value once, not three times.

The remedy is to match the direction to the problem. Each item at most once, the 0/1 knapsack, needs the loop downwards, from W to w. Each item as many times as wanted, the unbounded knapsack, such as coins or rolls of cable, needs it upwards, and then the upward reuse is exactly what is wanted. When in doubt, write the two-dimensional table, where the row above can never be overwritten.