Re: Bug#476340: ITP: datapacker -- Tool to pack files into minimum number of CDs/DVDs/etc
On Wed, Apr 16, 2008 at 12:21:51PM +, 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]
Re: Bug#476340: ITP: datapacker -- Tool to pack files into minimum number of CDs/DVDs/etc
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. ;-) -- brian m. carlson / brian with sandals: Houston, Texas, US +1 713 440 7475 | http://crustytoothpaste.ath.cx/~bmc | My opinion only troff on top of XML: http://crustytoothpaste.ath.cx/~bmc/code/thwack OpenPGP: RSA v4 4096b 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187 signature.asc Description: Digital signature
Bug#476340: ITP: datapacker -- Tool to pack files into minimum number of CDs/DVDs/etc
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 is useful, for instance, if you want to archive a number of files to CD or DVD, and want to organize them such that you use the minimum possible number of CDs or DVDs. . In many cases, datapacker executes almost instantaneously. Of particular note, the hardlink action can be used to effectively copy data into bins without having to actually copy the data at all. . datapacker is a tool in the traditional Unix style; it can be used in pipes and call other tools. -- System Information: Debian Release: lenny/sid APT prefers unstable APT policy: (500, 'unstable'), (99, 'experimental') Architecture: i386 (i686) Kernel: Linux 2.6.24-1-686 (SMP w/2 CPU cores) Locale: LANG=C, LC_CTYPE=en_US (charmap=ISO-8859-1) Shell: /bin/sh linked to /bin/bash -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]