News for hackers. Stuff that matters.

A comment on Are you up to the challenge? Dropbox wants to know. Parent comment

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?
[ Parent | on HN ]
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
[ Parent | on HN ]
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!
[ Parent | on HN ]
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!
[ Parent | on HN ]
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."
[ Parent | on HN ]
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....

[ Parent | on HN ]