Search code examples
algorithmpacking

Packing problem

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?

Solution

  • 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.