Sort file to fit on CD

[EdwinP]

My previous "Sort Collection into every Unique Combination" question showed me that what I want to do will take forever. But I had to see if my solution was the best way. It is not. What my end goal is, is to sort files (mp3, tif, ico, avi, wav) into groups that will fit on the least amount of floppies or CD's. I do not want to split them either. I was going to loop and sum their sizes until they match the floppy/cd size, then start a new group. By trying every combination, I would save the combination that contained the least amount of groups. My question is, is there a better way.
Thanks in advance,
Edwin

 

[fenris]

I have meant to do this, for the exact same reasons that you want to. But I have never gotten around to it.

Basically you want to maximize the number of files that you can fit onto an mp3!

I saw that my undergraduate engineering thesis would apply to this right away (Not directly though)! What you need is an optimization technique, from Operations Reasearch.

The mehtod that would work very, very well is called Genetic Algorithms....

I may be starting on it very soon if your interested.
Email me if you are interested with the details of this post. If you want to start on it I can probably email you some of my source code as example. BTW, if you goto

http://www.planetsourcecode.com

and do a search for my name you should find my code.

Regards...
Troy Williams B.Eng.
fenris@hotmail.com

 

[MichaelRed]

Troy,

Close but ...

In general the concept is to come as close to fillling the media as you possibly can - without going over the capacity. It doesn't matter wheather it is one file or 1.0E+99 files (at least in concept).

There are a number of messy details, but the process is simply to build sets (groups) of files where the total space occupied (Not the actual File SIZE) approximates the media capacity.

MichaelRed
mred@att.net

There is never time to do it right but there is always time to do it over

 

[fenris]

Michael,

In actuallity, the problem is identical to a classic knapsack problem. The idea behind the knapsack problem is that there is a knapsack that can carry a certain amount of weight. Your goal is to stuff as many objects (each object has it's own weight) into the knapsack with out exceeding the knapsacks weight capacity.

In the case of filling a cdrom, the weight would be the files volume in bytes.

<quote>
There are a number of messy details, but the process is simply to build sets (groups) of files where the total space occupied (Not the actual File SIZE) approximates the media capacity.
</quote>

With the GA scheme, the algorithm would be more or less straight forward and actually quite simple.

The hardest part would be creating the evaluation function, and I already have an idea on how to create it.

The representation of the packing order would be a binary string, i.e. 100111010101110 where each bit would represent a file and the state of the bit would indicate whether the file was included on the cd-rom or not.

If I find time this weekend I'll put together a demo of what I am talking about. if anyone is interested, email me...




Troy Williams B.Eng.
fenris@hotmail.com

 

[strongm]

This is a classic knapsack problem, and there are a variety of white papers and doctoral thesis on how to solve them effectively. Just do an internet search against 'knapsack problem' for additional information.