Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
vessenes
on Sept 14, 2010
|
parent
|
context
|
favorite
| on:
Are you up to the challenge? Dropbox wants to know
Interesting! It looks like none of them are optimal. Is this an NP-hard problem?
Keyframe
on Sept 14, 2010
|
next
[–]
That is an NP-hard problem.
http://en.wikipedia.org/wiki/Bin_packing_problem
kiuyhjk
on Sept 14, 2010
|
parent
|
next
[–]
The optimal solution then is to get an infinite number of people on the internet to solve it for you for free!
terraflop
on Sept 15, 2010
|
root
|
parent
|
next
[–]
Its an np-hard problem! Definitiv! And this is exactly what i thought!
irskep
on Sept 14, 2010
|
prev
[–]
Yes, there are several papers on the subject. I found a few by searching "rectangle packing algorithm."
harpastum
on Sept 14, 2010
|
parent
[–]
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....
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
