[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!


_______________________________________________
Tutor maillist  -  Tutor@[...].org
http://mail.python.org/mailman/listinfo/tutor