The loop order that changes the answer

Rolled to one dimension, the knapsack loop looks like this:

for each item:
    for w from W down to weight[item]:
        best[w] = max(best[w], value[item] + best[w - weight[item]])

Change one word, down to up, and you have solved a different problem. Both versions are correct; they answer different questions.

Why

Going downwards, best[w - weight] still holds the value from the previous item, because you have not reached it yet this round. So each item is used at most once. That is 0/1 knapsack.

Going upwards, best[w - weight] has already been updated this round, possibly with this same item. So the item can be used again. That is unbounded knapsack, where you have unlimited copies.

items: one 3kg item worth 5.  capacity 9.

downwards  ->  5   (used once)
upwards    ->  15  (used three times)

Why this page exists

This is the single most common source of wrong answers in dynamic programming, and it never produces an error. The program runs, prints a number, and passes the small examples. On [3kg, 5] with capacity 3, both directions give 5.

The difference only appears when an item could usefully be repeated, which is rarely the first test case anybody tries.

The habit

Before writing the inner loop, say which problem you are solving:

• Each item once means iterate capacity downwards.
• Unlimited copies means upwards.

And test with a capacity that is a multiple of an item weight, since that is the input where the two disagree.