Fog Creek Software
Discussion Board




Put 451 files (2.82 GB) on as few CDs as pos

I have 451 files in 19 folders worth 2.83 GB in all. Now I want to put all of that on a number of CDs. The files that cannot be separated are zipped together into one file.

What procedure should I follow to use as few CDs as possible?

This is a concrete question, and it reminds me of the water bottle question I posed several months ago.

Stefaan R. M. Meeuws
Sunday, April 04, 2004

Of course, I assume that every file would fit on an empty cd.

First I sort the files by size. I insert disc 1 and follow these steps:

1. Find the largest file that still fits on the current disc. If there is no such file, jump to step 4.
2. MOVE it to the disc. (I.e. it is not present anymore and thus won't be copied a second time.)
3. Go to 1.
4. You are finished with this disc. (Burn it / whatever.)
5. If there are any files left, insert a new cdr and go to 1.

Is it that obvious? Or have I missed anything?

Vigor
Sunday, April 04, 2004

This is the bin packing problem.

http://www.nist.gov/dads/HTML/binpacking.html
http://mathworld.wolfram.com/Bin-PackingProblem.html
http://www.cs.gsu.edu/~cscskp/Algorithms/NP/node11.html

Solving it optimally is NP-hard, so the best you will be able to do without extrardinarily expensive computation is approximate. The second and third links describe some heuristics that are commonly used.

Ham Fisted
Monday, April 05, 2004

You don't mention the capacity of the CDs. If it's 650MB or 700MB, then you will need  fiveCDs, and if its 800MB you will need four. If they are rewriteables then they will have a capacity of 535MB so you will need six.

Now, if your files totalled 2.79GB and the CDs were 700MB, then things would be more interesting.

Stephen Jones
Monday, April 05, 2004

DVD R/W?

code monkey
Saturday, June 26, 2004

*  Recent Topics

*  Fog Creek Home