You may have noticed that the knapsack problem in today’s comic has two solutions. I thought that (spoiler alert!) the 1, 0, 0, 2, 0, 1 solution was the only one, but 7, 0, 0, 0, 0, 0 — seven orders of mixed fruit — also works. Why did this happen? Well, I checked my numbers with a short Perl script (written while on vacation, with adorable kids climbing on me). It found the right answer in all my tests but broke when it really mattered. Witness the result of this line of Perl:
perl -e ‘print 2.15*7, “n”, 15.05, “n”, (2.15*7 == 15.05) ? “true” : “false”, “n”;’
15.05
15.05
false
Long story short, it claimed 2.15*7 did not equal 15.05, and so it missed the second answer in the search, though it found the first just fine
I know this sort of thing happens with floating-point math, but I didn’t expect it to break this badly and inconsistently on such a simple task. (edit: at that point, I was actually thinking of this as a weight problem (the variable was $weight), not a monetary problem, so separate cents math wasn’t an obvious choice).
Thank you to Chris Shabsin and Nick Moffitt for helping me pin down the problem.
xkcd 