A Wrong "Alternative" 0/1 Knapsack Solver

Be suspicious of algorithms given without proof of correctness, even if they do appear on the first page in Google.

An Alternative Dynamic Programming Solution for the 0/1 Knapsack is “alternative” as in homeopathy.  It’s appealingly somewhat simpler than the standard solution.

From their Java implementation:
// Initial guess:  the knapsack for wt-1.
   bestVal[wt] = bestVal[wt-1];
That already causes some sub-optimal solutions.  I fixed that, but that only reduced the frequency of wrong solutions.  For the input:

204
9
2 2
81 81
82 82
182 182
142 142
11 11
31 31
61 61
101 101

The “alternative solution” given is:
(142, 142)
(61, 61)
Total weight:  203
Total value:   203
But this is better:
(31+61+101 = 204)
The problem: the “alternative” solution has already used 31 in summing to (204-31), 61 in summing to (204-61), and 101 in summing to (204-101).  If the input is ordered differently, this may not happen - all 3 of those coincidences need to occur for the algorithm to fail.

The algorithm wrongly commits to just one way of reaching a given sum, unlike the standard (correct) solution.