[Tutor] A recreational math problem for Useless Python
Mon, 13 Aug 2001 03:27:45 -0400
> I've been glancing at Donald Knuth's neat "Selected Papers on Computer
> Science" and ran across an interesting problem that he presents. It
> sounds like a lot of fun, and perhaps someone might be interested in
> trying their hand at it. Here's the challenge problem (any mispelings
> are due to frantic typing): ...
It's an excellent problem, although I wish he would have left square roots
out of it (floating-point arithmetic complicates the problem to no good
There's a large and difficult literature on the "subset sum" problem, of
which this is an instance. That doesn't mean people should be scared away,
it means an exact solution is *so* hard ("NP-hard" in the jargon) that
*nobody* knows how to do it efficiently. So any stupid-ass <wink> trick you
can dream up is fair game. A "stupid-ass trick" is known as a "heuristic"
in the jargon, BTW, and finding good heuristics is a fascinating game.
After playing with this for a few years <wink>, you might want to check out
Bartosz Przydatek's 1998 subset-sum heuristic, available in a paper here:
The ideas there are very simple (honest <wink>), yet at the time it appeared
to be the best efficient approach known. I don't know whether something
better is known now. You may discover one!