Packing problem

Question

I want to write a little helper utility to organize my digitized audiobooks collection.

I have a set of folders which I need to write to CDs. The folders can not be split: each folder goes onto one disk.

I want to fill the disks most efficiently:

1. Minimize the number of disks, and
2. The number of disks being equal, maximize the storage available of the least filled disk (80 + 20 remaining space is better than 50 + 50).

Which algorithm should I use?

Answer 1

This is called the Bin Packing Problem and is NP-hard, so there is not a simple algorithm to solve it.

The solution I found worked best (I ran a programming contest with a question almost identical to this), was to order the folders by size and put the largest folder that still fits onto the disc until it is full or all remaining folders are too large to fit in the remaining space.

This solves the problem quickly since after the sort the rest of the algorithm is O(n).

In the contest I ran, this resulted in 74 discs instead of the 79 that a naive solution would achieve for our largest test data set.

Answer 2

If you would like to pack files/folders on one CD-R disc, than you could do this optimally in pseudo-polynominal time. To do this, you have to round sizes of files/folders into sectors, and count sectors available on CD-R.

After this, we get discrete 1-D knapsack packing problem, which can be solved nicely using dynamic programming, with complexity O(n),

To be more specific:

• O(n) = O(nW) , cause W is constant in your case - W is amount of sectors on CD-R.
• n amount of files/folders.

For better performance you can always over-approximate size of sectors, example setup:

• over-approximated sector size 70k
• what makes 700M/70k = 10k of all sectors on CD-R
• which should compute in seconds when amount files less than (1G/10k=100k) 100k - n < 100'000
• in minutes when n < 10'000'000

What's more:

• solution can be nicely paralleled.

Maybe applying this algorithm in greedy manner "pack one cd, pack next cd" will do it's work?