# [Tutor] A recreational math problem for Useless Python

**Tim Peters
**
tim.one@home.com

*Mon, 13 Aug 2001 03:27:45 -0400*

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