akcs.joehorn@hpcvbbs.UUCP (Joseph K. Horn) (03/19/91)
Help! Here's a problem desperately seeking a solution: I want to make a cassette tape containing songs of different lengths. Which songs do I put on which sides so as to insure that both sides are the same length (or as close to the same as possible)? We have one solution that involves recursion, but it's not exciting to watch... Is there a way of doing this that doesn't take minutes to run? The applications for a "goal seeking engine" like this are many; the classic postage stamp problem; checkbook balancing... -- Jeff Duncombe -- Joseph Horn -- & the PPC gang
NORM%IONAACAD.BITNET@CUNYVM.CUNY.EDU (Norman Walsh) (03/20/91)
Joe,
This sounds vaguely reminicent of a problem that I posted to another
list. I was looking for the best algorithm for putting files onto
floppy disks. It was neatly demonstrated by several people that this
is an np-complete problem with no clear algorithmic solution. The
agreed-upon best solution was the following: sort the songs in descending
order order by length. Put the longest song that will fit on the side
with the most remaining space. Repeat until you run out of songs (or
space).
ndw