Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  A.Schulz Nov 10 '12 at 19:41
1  
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? –  Paresh Nov 10 '12 at 19:47
1  
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. –  Paresh Nov 10 '12 at 21:10
    
@Paresh is this variation known to be NP-hard? –  Bitwise Nov 11 '12 at 1:28
    
@Bitwise I am not sure. –  Paresh Nov 17 '12 at 10:29
add comment

2 Answers

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.

share|improve this answer
    
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. –  user742 Nov 12 '12 at 9:23
add comment

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 :)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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