 | | From: | Heiner Steven | | Subject: | Algorithm for distributing files on multiple CD-ROMs | | Date: | Thu, 20 Jan 2005 09:05:09 +0100 |
|
|
 | [If this is the wrong news group, please direct me to a right one]
Hello,
I'm searching for an algorithm for distributing many large files
on potentially several CDs.
Example:
o CDs have the size 100 MB (for easier calculations)
o Three files should be written on the CDs
file A - 60 MB
file B - 90 MB
file C - 30 MB
The goal is to use as few CDs as possible.
- A bad algorithm (writing files in the order of their file name)
requires 3 CDs, with each CD containing only 1 file.
- A better algorithm would recognize that file A and file C both fit
on one CD, and result in a total number of 2 CDs.
A naive approach would create all permutations of all files, and
weight each permutations with the number of CDs needed, e.g.
A B C = 3 CDs
A C B = 2 CDs
B A C = 3 CDs
[...]
C A B = 2 CDs
This would show that A C B and C A B are both permutations resulting
in the minimum number of CDs, 2.
The full enumeration of all permutations is no feasible approach
though, because the number of permutations is n! and increases very
rapidly: for 10 files it already has to check 3628800 cases.
I'm searching for an (perhaps heuristic) algorithm that works for
a larger number of files (order of 10000), too.
Heiner
--
___ _
/ __| |_ _____ _____ _ _ Heiner STEVEN
\__ \ _/ -_) V / -_) ' \ Shell Script Programmers: visit
|___/\__\___|\_/\___|_||_| http://www.shelldorado.com/
|
|
| | From: | Michael Jørgensen | | Subject: | Re: Algorithm for distributing files on multiple CD-ROMs | | Date: | Thu, 20 Jan 2005 09:26:50 +0100 |
|
|
|
"Heiner Steven" wrote in message
news:41ef6441$0$17603$9b4e6d93@newsread4.arcor-online.net...
> [If this is the wrong news group, please direct me to a right one]
>
> Hello,
>
> I'm searching for an algorithm for distributing many large files
> on potentially several CDs.
This is a well known problem, known as "bin packing". Google gives many
hits.
-Michael.
|
|
| | From: | Heiner Steven | | Subject: | Re: Algorithm for distributing files on multiple CD-ROMs | | Date: | Sat, 22 Jan 2005 10:46:10 +0100 |
|
|
| Michael Jørgensen wrote:
[...]
> "Heiner Steven" wrote in message [...]
>>I'm searching for an algorithm for distributing many large files
>>on potentially several CDs.
>
> This is a well known problem, known as "bin packing". Google gives many
> hits.
Another name for it is "knapsap" problem. There are many theoretical
texts about it. For me, the most helpful would be source code
or a description of an algorithm.
Heiner
|
|
| | From: | Randy Howard | | Subject: | Re: Algorithm for distributing files on multiple CD-ROMs | | Date: | Sat, 22 Jan 2005 12:52:24 GMT |
|
|
| In article <41f21ee2$0$17613$9b4e6d93@newsread4.arcor-online.net>,
heiner.steven@nexgo.de says...
> Michael Jørgensen wrote:
>
> [...]
> > "Heiner Steven" wrote in message [...]
>
> >>I'm searching for an algorithm for distributing many large files
> >>on potentially several CDs.
> >
> > This is a well known problem, known as "bin packing". Google gives many
> > hits.
>
> Another name for it is "knapsap" problem.
knapsack. GIYF.
--
Randy Howard (2reply remove FOOBAR)
|
|
