[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

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: