## 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:

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

204The “alternative solution” given is:

9

2 2

81 81

82 82

182 182

142 142

11 11

31 31

61 61

101 101

(142, 142)But this is better:

(61, 61)

Total weight: 203

Total value: 203

(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.