C#: Code to fit LOTS of files onto a DVD as efficiently as possible

Question

I need to write an application that will take a list of files (some large, some small) and fit them onto DVDs (or CDs, or whatever) as efficiently as possible. The whole point of this application is to use up as much of the 1st disc before moving onto the 2nd disc, filling the 2nd disc up as much as possible before moving onto the 3rd disc, etc.

(Note: The application doesn't have to do the actual burning to the DVD, it just has to figure out the best possible fit).

I initially thought I had a good game-plan by generating a permutation of the files and then checking each combination to see what fits the best. (My request for help on this can be found HERE)

But the more files there are, the longer it takes... exponentially. So I wanted some of your opinions on how to best achieve this.

I feel helpless with this project.

Any ideas? And, as always, C# code is always appreciated.

Thanks!

Answer 1

What you're facing is related to the knapsack problem. The linked wikipedia page has lots more information, including suggested ways of solving it.

Answer 2

for each file
 is there enough room this dvd?
   yes, store it here
   no, is there room on another already allocated dvd?
     yes, store it there
     no, allocate another dvd and store it there

Answer 3

Simple algorithm:

1. Sort the file list by file size
2. Find the largest file smaller than the remaining free space on the DVD, and add it to the DVD.
3. If the remaining DVD free space is smaller than any remaining files, start a new dvd.
4. Repeat from 2.

Answer 4

While thats a cool problem to solve in a program for certain applications... however in your application, why not just use WinRAR or some other archiving program that has the capability to split up the archive into specific sized file chunks. You could make each chunk the size of a DVD and then just burn away.

EDIT: one issue you would run into is that if one of your files is greater than the size of your media, you are not going to be able to burn that file.

Answer 5

How about if you started by putting as many of the largest files you can onto one DVD and then filling it up with as many of the smallest files that you can (starting with the smallest).

Repeat this process with the remaining files for each disk.

I'm not sure that's going to give you perfect coverage/distribution but I think it might go some way to solving your needs.