FAQ Search Today's Posts Mark Forums Read
» Video Reviews

» Linux Archive

Linux-archive is a website aiming to archive linux email lists and to make them easily accessible for linux users/developers.


» Sponsor

» Partners

» Sponsor

Go Back   Linux Archive > Debian > Debian Development

 
 
LinkBack Thread Tools
 
Old 04-16-2008, 12:21 PM
"brian m. carlson"
 
Default 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 <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. ;-)


--
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
 
Old 04-16-2008, 06:13 PM
Jon Leonard
 
Default 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


--
To UNSUBSCRIBE, email to debian-devel-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
 

Thread Tools




All times are GMT. The time now is 11:33 AM.

VBulletin, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO ©2007, Crawlability, Inc.
Copyright 2007 - 2008, www.linux-archive.org