To: Jerry Yu... Re: [ale] 2 Perl questions ?

[Aditya Srinivasan]

On Wed, 15 Dec 2004, attriel wrote:

> > Yes.  It's been a while since my CS algorithms course, but I believe
> > this is known as the knapsack problem.  I think the general knapsack
> > problem is NP complete, but it can be partitioned in such a way that you
> > could solve this particular problem using dynamic programming.
> 
> I always learned it as the box-packing algorithm, which is NP-complete
> only as regards an "optimal" solution.


Yup, this seems to be the correct problem.

http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE192.HTM
*********************************************
Input description: A set of n items with sizes  . A set of m bins with 
capacity  . 

Problem description: How can you store all the items using the smallest 
number of bins? 

Discussion: Bin packing arises in a variety of packaging and manufacturing 
problems.     Suppose that you are manufacturing widgets with parts cut 
from sheet metal, or pants with parts cut from cloth. To minimize cost and 
waste, we seek to lay out the parts so as to use as few fixed-size metal 
sheets or bolts of cloth as possible. Identifying which part goes on which 
sheet in which location is a bin-packing variant called the cutting stock 
problem.   After our widgets have been successfully manufactured, we will 
be faced with another bin packing problem, namely how best to fit the 
boxes into trucks to minimize   the number of trucks needed to ship 
everything. 
*********************************************


Now it seems obvious that this would be a common problem for the packaging 
industry.

I've noticed often that some of the stuff I buy is very creatively 
packaged to save space. I wonder if a partial mathematical approach is 
used by the packaging industry to solve these problems.

More from the article :

*********************************************

Packing boxes is much easier than packing arbitrary geometric shapes, 
enough so that a reasonable approach for general shapes is to pack each 
part into its own box and then pack the boxes. Finding an enclosing 
rectangle for a polygonal part is easy; just find the upper, lower, left, 
and right tangents in a given orientation.   A minimum-area enclosing 
rectangle can be found by determining the orientation that leads to the 
smallest box. 
*********************************************

Interesting problem domain.

-- 
Thanks,
sriad