3 ms·

It's called The Knapsack Problem - and optimizing it is NP hard https://en.wikipedia.org/wiki/Knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem

• eru 9y ago
  Solving the knapsack problem for practical instances is actually really easy. (That's a general pattern with NP hard problem: most of them are easy in practice.) But the problem described is closer to two- or three-dimensional bin packing (or scheduling in general) than to the knapsack problem. See eg http://www.research.ibm.com/people/n/nikhil/papers/Bansal-packing.pdf http://www.research.ibm.com/people/n/nikhil/papers/Bansal-pa... Another thing to look at is the "Cutting stock" problem (https://en.wikipedia.org/wiki/Cutting_stock_problem https://en.wikipedia.org/wiki/Cutting_stock_problem).
• laksjd 9y ago
  Knapsack is only about weight, while this is about (most likely) packing 3D cuboids. But that problem is NP-hard, too ;)
  • gaius 9y ago
    All shipping containers are an identical size - it is a weight problem.
    • tesseract 9y ago
      The original discussion about ships was, but this comment thread was about packing (retail packaged) products into a shipping carton.