# comp.graphics.algorithms

## Subject: Re: BIN Packing Problem

"Howie" wrote in message
> Hi,
>
> i'am serching an algorithm to solve this problem:
>
> There are a several pieces of an article (think of apples). There are
> types of boxes to pack the articles in. There can different sizes of
> boxes if there are other articles.
> How the get the best count of boxes of each size.
>
> Example:
> 7 apples, boxtypes are 3-size and 2-size.
> Getting 2x 3s and 1x2s would remain 1 piece over.
> Best would be: 1x3s and 2x2s boxes wich remains non rest.
>
> or:
> 16 oranges, boxtypes are 20-size, 3-size and 2-size.
> Best Fit: 0x20s and 4x3s and 2x2s
>
>
> Thanks in advance,
>
> Howie

This isn't exactly a graphics problem, but hey, why not.

Your problem is a special case of the Knapsack problem, an NP-hard problem.
However, there exists a dynamic programming solution to solve the problem in
O(n^2) time, so we'll have a look at that one.

I will define the problem according to the Knapsack problem definition:

Given a set of objects U={u[1], u[2], ..., u[n]}, each with a corresponding
value={v[1], v[2], ..., v[n]}, and size={s[1], s[2], ..., s[n]}, a value
goal V for the knapsack, and some knapsack size S. Can we choose some
subset of objects such that the total size of the objects chosen does not
exceed the knapsack size while meeting or exceeding the desired value?

Let's start by saying that the object set U is actually going to be the
boxes you choose, and not the apples or oranges, and you will have n boxes,
to be defined later. Also, for this problem, I want v[i]=s[i] for 1<=i<=n.
The value goal V and the size of the knapsack are going to be assigned the
value of the size of the number of objects you have (i.e., 7 apples or 16
oranges).

First, we notice that you can have any number of boxes since you didn't
constrain us (which is actually a trivial extension to the dynamic
programming solution). Therefore, for each box size, we want to have
exactly ceiling (S/box size) boxes available. This will allow me to choose
as many boxes of one size as needed to completely store all of the objects
you have. In other words, in your second example of 16 oranges, we would
want ceiling (16/20)=1 box of size 20 available, ceiling (16/3)=6 boxes of
size 3 available, and ceiling (16/2)=8 boxes of size 2 available. This will
allow us to choose all six boxes of size 3 to store 16 oranges, for example,
with an excess of 2 size units unused. The sum of these values is to be
stored in n. Again, for example 2, n=1+6+8=15. This value of n is the
total number of boxes we have available to us. Also, let J denote the size
of the maximum of the respective ceilings multiplied by the respective box
sizes (max {1*20=20, 6*3=18, 8*2=16}=>20).

Next, we want to define each v[i] and s[i] for 1<=i<=n. Each of these
values is to be the size of box i.

So, we now have the problem defined. How do we determine the solution?

We will construct a table T of size (n+1) rows and J+1 columns. The values
in the table are all initially set to 0, except t[0, 0] which is set to 1.
A value of 1 in a particular place t[i, j] indicates that it is possible to
obtain the specific value of j using some subset U' of objects from U.

The algorithm otherwise is as follows:

for (i=0; i<=n; i++) {
for (j=0; j<=J; j++) {
if ((t[i-1, j-v[i]]+v[i]==j) || (t[i-1, j]==1)) {
t[i, j]=1;
}
}
}

If t[n, V] is 1, you have an exact solution. Otherwise, your minimum
solution will be to the right of t[n, V]. To find your minimum solution,
you need to work your way up the table. If t[i-1, j]!=1, you add item i to
U' (that is, you want to pick a box of size v[i]), and then set j=j-v[i].

I created your second example as such a problem, and solved it, to give you
an example of the algorithm. The first row corresponds to the values of j.
Each subsequent row starts with the value v[i] of box i, and then a 1 or a 0
if the value j can be found at t[i, j] using some subset of items from the
current and previous row. Each row is in quotes, to avoid confusion of
wrap-around.

" 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20"
"0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
"20 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1"
"3 1 0 0 *1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1"
"3 1 0 0 1 0 0 *1 0 0 0 0 0 0 0 0 0 0 0 0 0 1"
"3 1 0 0 1 0 0 1 0 0 *1 0 0 0 0 0 0 0 0 0 0 1"
"3 1 0 0 1 0 0 1 0 0 1 0 0 *1 0 0 0 0 0 0 0 1"
"3 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1"
"3 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1"
"2 1 0 1 1 0 1 1 0 1 1 0 1 1 0 *1 1 0 1 1 0 1"
"2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 *1 1 1 1 1"
"2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"
"2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"
"2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"
"2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"
"2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"
"2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"

To determine the optimal combination of boxes you would need to first find
position t[15, 16] and determine if it is a 1. It is, so an optimal value
exists. (If it didn't, the next best value would be to the right of t[15,
16].) To find the first item to pick, we go up the table to find a change
from 1 to 0. This happens at t[9, 16], so we go left a value of v[i], or 2.
It happens again at t[13, 14], and so on. Eventually, our subset U'={u[9],
u[8], u[5], u[4], u[3], u[2]}. Matching the sizes of the boxes, we get 2
boxes of size 2 and four boxes of size 3. 2*2+4*3=16, your value goal.

So, remember, this is a pseudo-polynomial time algorithm, because for large
value boxes, your table T is not bounded by the number of boxes you have but
instead by the values of the boxes themselves, which is not
polynomially-related to the number of boxes. In other words, although you
are guaranteed an exact solution, this is not a truly O(n^2) algorithm.

I better pass my NP-completeness course and qualifying exam now. ;)

Take care,

Cliff Hewitt