what is the algorithm to optimally fill a dvd for burning

Question

What is the optimal algorithm for filling a set of Blu-ray disc given many hundred gigabytes of assets of varying sizes?

I am trying to consolidate a large number of old CDROMS, DVDs and small hard drives and put everything in a database indexed by MD5 signature. A daunting task for sure.

What I currently do is to sort the asset sizes (usually directory sizes) in descending order, start inserting the largest assets in the fill list skipping any that don't fit until I run out of assets. It runs almost instantaneously but I would not mind running overnight if necessary one time.

It usually gives me 95% or more utilization, but I am sure there is a way to use other combinations to give a higher efficiency. With huge items like disk images, I can get quite low utilization with this primitive method.

My thought is to take all combinations of the assets taken, 1 then 2, then 3, ... items at a time and keep a running value for the highest byte count < 25,025,314,816 bytes pointing to the array which sums to it. When I get to the point that I have so many assets taken at one time that none of the combinations will fit, stop and use the array pointed to by the running highest counter.

Is this the best possible algorithm?

There are 2 Perl modules which seem up to the task, Algorithm-Combinatorics and Math-Combinatorics. Any advice on which is faster, more stable, cooler?

My scheme is to write a script to calculate the sizes of a large number of directories and show me the optimal contents of the dozens of disks to burn.

And, I don't want to just fill on a file by file basis as I want entire directories on the same disc.

Answer 1

This is an NP-complete problem known as bin packing. There is no known polynomial-time algorithm that solves it optimally. In other words, the optimal solution cannot be found without basically trying all solutions.

On the plus side, a very simple heuristic like "put the largest remaining folder on the first disk that has room" will guarantee that you will use fewer than twice as many disks as the best case. (You can read more details on the problem's Wikipedia article).