Re: Distribute MP3 recordings optimally to CD-Rs

It seems this problem would be best solved by sorting your data biggest to smallest. Then just go over the list picking the next file that still fits in the space you have left. That should be pretty straight forward and fast. /me begins working on a general solution.

___________
Eric Hodges

Comment on Re: Distribute MP3 recordings optimally to CD-Rs

Replies are listed 'Best First'.
Re^2: Distribute MP3 recordings optimally to CD-Rs by MidLifeXis (Monsignor) on Sep 30, 2005 at 16:36 UTC
... which is one of the classical "good try" solutions to the knapsack problem. --MidLifeXis	[reply]
Re^2: Distribute MP3 recordings optimally to CD-Rs by revdiablo (Prior) on Sep 30, 2005 at 19:26 UTC
That's basically the algorithm I used in Algorithm::BinPack. Sort by biggest-first, then iterate on each item. If it doesn't fit in the first bin, try the next bin. Rinse, repeat.	[reply]
Re^3: Distribute MP3 recordings optimally to CD-Rs by tweetiepooh (Hermit) on Oct 06, 2005 at 09:09 UTC
Don't know if this is relevant but do you need to allow space for overheads like directories etc? Is that part of the rough 700Mb per CD? Does that overhead change with number of files? ie can you fit 2 x 349 Mb files (698Mb) but only 195 x 3.49 Mb (680Mb). Doesn't really change the principal behind the algorithm. Although not directly relevent to computer files there is also the issue of retrieval. The best packing method my be less efficient if the files you most want to retrieve are scattered. This is part of programming for loading a lorry for a drop load. You need to make the best packing but also take into account the best route for the drop and how they will get stuff off.	[reply]
Re^2: Distribute MP3 recordings optimally to CD-Rs by Brutha (Friar) on Oct 10, 2005 at 13:42 UTC
That was my manual solution, but it is not the best. Think of having sizes of 5,4,3,2 to fit on a 10 unit disk. After (5,4) nothing will fit, but (5,3,2) is better. That is the reason, why I try to check all solutions. And it came to pass that in time the Great God Om spake unto Brutha, the Chosen One: "Psst!" (Terry Pratchett, Small Gods)	[reply]