Geek Answers Handbook

Packaging problems

I want to write a little helper utility to organize my collection of digital audio books.

I have a set of folders that I need to burn to CDs. Folders cannot be divided: each folder goes to one drive.

I want to fill the disks most efficiently:

  • Minimize the number of drives and
  • An equal number of disks maximizes the available storage of the least full disk ( 80 + 20 remaining space is better than 50 + 50 ).

Which algorithm should I use?

+4
source share
2 answers

This is called the bin packing problem and NP-hard, so there is no simple algorithm to solve it.

The solution I found worked best (I held a programming contest with a question almost identical to this), consisted in sorting the folders by size and placing the largest folder that still fits on the disk until it is full or all other folders are too large to fit into the remaining space.

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

In the competition I ran, this led to 74 discs instead of 79, which a naive solution would have achieved for our largest test suite.

+4
source

If you want to pack files / folders onto one CD-R disc, then you can do this optimally in pseudo-polynomial time. To do this, you need to combine the file / folder sizes in the sectors and calculate the sectors available on the CD-R.

After that, we get the discrete packing problem for a 1-D backpack , which can be easily solved using dynamic programming, with complexity O (n),

More specific:

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

For best performance, you can always override the size of sectors, for example, setup:

  • overly approximate sector size of 70 thousand
  • making 700M / 70k = 10k of all sectors on a CD-R
  • which should be calculated in seconds when the number of files is less than (1G / 10k = 100k) 100k - n <100'000
  • in minutes when n <10'000'000

What else:

  • Decision
  • can be well matched.

Perhaps applying this algorithm in the greedy way of "pack one CD, pack next cd" will it work?

+2
source

More articles:


All Articles