Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?

Re^3: How to maximise the content of my data CD

by Limbic~Region (Chancellor)
on Feb 25, 2005 at 14:40 UTC ( #434485=note: print w/replies, xml ) Need Help??

in reply to Re^2: How to maximise the content of my data CD
in thread How to maximise the content of my data CD

Eimi Metamorphoumai,
Won't always work,...

What I didn't say explicitly, but was implied by my bullet points was that 1 disc is being added to account for perfect (or even near perfect fits). The knapsack problem is hard but we aren't trying to break encryption we are trying to save a few pennies on CDs. I don't think (though I could be wrong) that it will ever waste more than 1 disk. Too make matters more difficult, we aren't talking about a handful of files but more likely hundreds if not thousands. Let's say that the total size is an exact multiple of 1 CD. That means every single CD needs to be an exact match (which may not even be possible). Proving it can or can not might take a while (extreme sarcasm). Why not just go with a "good enough" solution?

Update 2008-11-26: It turns out that this heuristic approach can be is much as 11/9 OPT + 1 bin (according to bin packing). While my experience has been that 1 extra is all you will ever need, it is possible to need more.

Cheers - L~R

  • Comment on Re^3: How to maximise the content of my data CD

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://434485]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (9)
As of 2021-02-26 13:25 GMT
Find Nodes?
    Voting Booth?

    No recent polls found