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 +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 <jgoerzen@complete.org>
>>
>> * Package name : datapacker
>> Version : 1.0.0
>> Upstream Author : John Goerzen <jgoerzen@complete.org>
>> * 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
Reply to: