Hacker News Reader

Does anyone know if this problem is NP-Complete? It sounds fairly similar to the knapsack problem, so much so that this might be as hard as said problem. However, I'm not sure if these specific conditions could be shown to be in NP.

View on HN

It sounds like the issue is not optimal packing, but rather getting the cheese into the same box as the cereal without making the cheese spoil.

My hopes of mentally writing this off as a straightforward implementation exercise of well-known optimization heuristics have been spoiled. Maybe I couldn't have just sat down and banged it out in a few days with a little Googling and going over old college lecture notes. Damn you, Hacker News!

Indeed, I thought this was going to be an interesting application of the knapsack problem. Instead, this quote leads me to think it's the inherent difficulties of concurrency and synchronization:

"We had to write an enormous amount of code," Mr. Ackerman said, "because any one of 10,000 products can go to any point at any time."

bin packing problem is NP hard right? http://en.wikipedia.org/wiki/Bin_packing_problem

Reply on news.ycombinator.com