On Wed, Apr 16, 2008 at 12:21:51PM +0000, brian m. carlson wrote: > On Tue, Apr 15, 2008 at 10:50:23PM -0500, John Goerzen wrote: >> Package: wnpp >> Severity: wishlist >> Owner: John Goerzen <[EMAIL PROTECTED]> >> >> * Package name : datapacker >> Version : 1.0.0 >> Upstream Author : John Goerzen <[EMAIL PROTECTED]> >> * URL : http://software.complete.org/datapacker >> * License : GPL >> Programming Lang: Haskell >> Description : Tool to pack files into minimum number of CDs/DVDs/etc >> datapacker is a tool to group files by size. It is >> designed to group files such that they fill fixed-size containers >> (called "bins") using the minimum number of containers. > > This sounds suspiciously like the knapsack problem, which is in NP. Is > it guaranteed to use the minimum number, or are there cases when it > would not? If the former, I'm sure Merkle and Hellman would like to > hear from you. ;-)
If all the items to be packed are multiples of a common size (say, one sector on a CD), then it is instead an instance of "integer knapsack", which has a dynamic programming algorithm of reasonable complexity. (That is, number of items times bin size.) It's entirely possible that datapacker solves the problem that way. Jon Leonard -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]