4
$\begingroup$

I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains as many as possible?

  • No rotation is allowed.
  • The heavier boxes must not be on the top of the lighter ones.
  • Approximation is allowed.

I am looking for the algorithm so I can implement it in a software.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Please give more information: Have the boxes to be axis-aligned, or is it okay to rotate them. Are you interested in the computational complexity of the problem or in algorithms or in both? $\endgroup$
    – A.Schulz
    Nov 10, 2012 at 19:41
  • 1
    $\begingroup$ This is a NP-hard problem, and so exact solutions are possible only for small instances. Do you want approximation algorithms or heuristics or optimal (exact) algorithms only? $\endgroup$
    – Paresh
    Nov 10, 2012 at 19:47
  • 1
    $\begingroup$ If you leave aside the criteria of heavier ones below lighter ones, this problem becomes the NP-hard 3D orthogonal knapsack problem, for which you can find approximation algorithms easily. Maybe you can get some hints for your specific case from that. Also, I believe a branch-and-bound based exact algorithm might also work for small inputs: as you have edited the question with the weight criteria, it might result in faster pruning/bounding of the search tree. $\endgroup$
    – Paresh
    Nov 10, 2012 at 21:10
  • $\begingroup$ @Paresh is this variation known to be NP-hard? $\endgroup$
    – Bitwise
    Nov 11, 2012 at 1:28
  • $\begingroup$ @Bitwise I am not sure. $\endgroup$
    – Paresh
    Nov 17, 2012 at 10:29

2 Answers 2

Reset to default
3
$\begingroup$

Your problem is called 3D Bin Packing and is indeed an NP problem.

Looking those key words on Google will yield many articles about more or less complex approximation algorithms that can help you solve this problem.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ May be this is good intuition on problem, but it's not an answer. At least provide some link in your answer, or explain how it's NP-Hard. Also OP was also interested in approximations. $\endgroup$
    – user742
    Nov 12, 2012 at 9:23
0
$\begingroup$

Your problem is called (multiple constraints) knapsack problem and is indeed an NP problem.

Looking those key words on Google will yield many articles about more or less complex approximation algorithms that can help you solve this problem :)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.