Re:Are you up to the challenge? Dropbox wants to know
by vessenes on Tuesday September 14, 2010 @03:37PM
(#1691954)
Interesting! It looks like none of them are optimal. Is this an NP-hard problem?
Re:Are you up to the challenge? Dropbox wants to know
by Keyframe on Tuesday September 14, 2010 @03:44PM
(#1691992)
That is an NP-hard problem. http://en.wikipedia.org/wiki/Bin_packing_problem
Re:Are you up to the challenge? Dropbox wants to know
by kiuyhjk on Tuesday September 14, 2010 @04:19PM
(#1692117)
The optimal solution then is to get an infinite number of people on the internet to solve it for you for free!
Re:Are you up to the challenge? Dropbox wants to know
by terraflop on Wednesday September 15, 2010 @06:40AM
(#1693843)
Its an np-hard problem! Definitiv! And this is exactly what i thought!
Re:Are you up to the challenge? Dropbox wants to know
by stevejohnson on Tuesday September 14, 2010 @03:47PM
(#1692010)
Yes, there are several papers on the subject. I found a few by searching "rectangle packing algorithm."
Re:Are you up to the challenge? Dropbox wants to know
by harpastum on Tuesday September 14, 2010 @03:50PM
(#1692021)
Although I didn't read it until after I had created my solutions, I found Andrea Lodi's paper [1] very interesting. It wasn't quite the approach I used, but it's a pretty thorough explanation of the problem and possible solutions.
[1] PDF http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98....
Re:Are you up to the challenge? Dropbox wants to know
by asmosoinio on Wednesday September 15, 2010 @04:02AM
(#1693659)
That url gives me this responce: "Request timed out -- This application failed to respond within 30 seconds."
You can play with them here: http://dbpacker.samwarmuth.com/ (make sure to scroll horizontally to see all of them -- there are 10 different methods)
I'm planning on doing a short write-up of the process once they remove it from their jobs page.