[Tutor] A recreational math problem for Useless Python

[Tim Peters]

[Danny Yoo]
> 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
end).

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:

    http://www.cs.cmu.edu/~bartosz/subset/

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!