Re: Help with Space Efficency algorithim

[LighthouseJ]

I looked at this independently in the perspective of fitting files onto a DVD. I ended up programmatically brute-forcing it (which takes a long time of course because it has to check all possible cases) but it ended up with the best results possible. Brute force might not be bad since you have only about 5 things, so that's only 5! (I think) cases to try.
Sure, algorithms like ordering the sizes or randomly placing things together would save time but there's no shortcut to the best result.

[Anonymous Monk]

> there's no shortcut to the best result.

Laziness -- brute force (exhaustive combination) is perhaps easiest to code (although first fit decreasing is pretty easy)

Impatience -- exhaustive combination dies a horrible flaming death somewhere in the high teens, unless your computer is a lot faster than mine. First Fit Decreasing needs a sort, but that isn't a big deal until you get into too many DVDs to want to hand process.

Hubris -- exhaustive combination will achieve the optimal result, but first fit decreasing will come within 11% of it. What price glory?

[LighthouseJ]

heh. well, as I see it, laziness applies to execution, not ease of programming. Impatience is more of a direct result of taking shortcuts, i.e. utilizing a sorting algorithm. I'm not looking for glory, just the best answer.

I don't know about you but I don't get the luxury of living 11% away from correct.