What is the easiest way to organize luggage?
Problem Description:
I have a probleme about organizing luggage. I know to volume of the luggage and each item that I will put in to the luggage. When I calculate it I see that it is possible to fit them in to the luggage. But I don’t know how to do it? (Also I know the shapes of the items.)
Solution – 1
This problem is well known enough to deserve a Wikipedia article: Knapsack problem.
Quoting the article:
The knapsack problem is interesting from the perspective of computer science for many reasons:
The decision problem form of the knapsack problem (Can a value of at least V be achieved without exceeding the weight W?) is NP-complete, thus there is no known algorithm that is both correct and fast (polynomial-time) in all cases.
While the decision problem is NP-complete, the optimization problem is not, its resolution is at least as difficult as the decision problem, and there is no known polynomial algorithm which can tell, given a solution, whether it is optimal (which would mean that there is no solution with a larger V, thus solving the NP-complete decision problem).
There is a pseudo-polynomial time algorithm using dynamic programming.
There is a fully polynomial-time approximation scheme, which uses the pseudo-polynomial time algorithm as a subroutine, described below.
Many cases that arise in practice, and "random instances" from some distributions, can nonetheless be solved exactly.
Solution – 2
Hint:
In its full geometric embodiment (objects of known 3D shape), the packing problem is virtually intractable if you want an exact solution.
You must simplify it, for instance by approximating the objects by a bounding box and disallowing arbitrary rotations. Then, there is no much better way than brute force trials.