**comp.graphics.algorithms**

## Subject: **Re: BIN Packing Problem**

"Howie"

news:1146749228.131556.251100@j33g2000cwa.googlegroups.com...

> 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

Reply

View All Messages in

**comp.graphics.algorithms**

path:

BIN Packing Problem =>

Replies:

Re: BIN Packing Problem

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.