Solved

# An algorithm to deposit boxes

Posted on 2000-01-09
Medium Priority
262 Views
I am not sure it is a question for DELPHI.
There are three boxes:
BoxA(Height=nAHeight,NUM=nANum),
BoxB(Height=nBHeight,NUM=nBNum),
BoxC(Height=nCHeight,NUM=nCNum),
now pick at least each of them to deposit to a fixed height(nHeightWanted), and make the error smallest.

I wrote the following code,is there a better way?

procedure procPick;
var
I,J,K : Integer;
rMin,rTemp : Real;
IJKList : TStrings;
begin
IJKList : TStringList.Create;
rMin := nAHeight;

for I := 1 to nANum
for J := 1 to nBNum
for K := 1 to nCNum
begin
rTemp := nHeightWanted - nAHeight*I - nBHeight*J - nCHeight*K;
if(rTemp < 0) then Break;

if(rTemp <= rMin) then
begin
if(rTemp < rMin) then
IJKList.Clear;
end;
end;

{something else}

IJKList.Free;
end;
0
Question by:zxw
• 6
• 5

Author Comment

ID: 2347649
0

LVL 1

Expert Comment

ID: 2352850
Hi zxw,

It is strange fact that there are no comments yet.This is not question especially for DELPHI but for PROGRAMMING generally and I find it more interesting than say 90% of questions posted here because it is not technological but algorithmical one.

On the question: Yes, there is a better way, named Recursion (the best I know). I need a couple of hours to think over your question in order to put here some code, but now have to go out. If you are patient until Monday, and nobody else do it, I'll see you again :-).

Jo.
0

Author Comment

ID: 2358062
Mr. fatman,

You can see now how patient I am waiting and how eager I am to see you again!
0

Author Comment

ID: 2358085
And i just lost a line :
rMin := rTemp

to set the rMin to the smallest error value as fowlling:

if(rTemp <= rMin) then
begin
if(rTemp < rMin) then
IJKList.Clear;

rMin := rTemp;

end;
end;
0

LVL 1

Expert Comment

ID: 2358999
Hi zxw,

Here I'm posting a code I've just written.It is not much adjusted, but I thik it should give you an idea about what I'm talking.
The core, as you can see, is the procedure PlaceNext, which is recursively calling itself.

Parameters are as follows:
H1,H2,H3 - the height of every kind of boxes;
N1,N2,N3 - the count of currently placed (initial values: 0);
M1,M2,M3 - the number of boxes of every kind;
MaxErr - maximal allowed error (free height);
FreeHeight - currently free height of the boxes container;
List - StringList variable where you get results;

---------cut here------------

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, Buttons;

type
TForm1 = class(TForm)
ListBox1: TListBox;
SpeedButton1: TSpeedButton;
Label1: TLabel;
procedure PlaceNext(H1,H2,H3:Real;N1,N2,N3,M1,M2,M3:Integer;MaxErr,FreeHeight:Real;var List:TStringList);
procedure SpeedButton1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;

implementation

{\$R *.DFM}

procedure TForm1.PlaceNext(H1,H2,H3:Real;N1,N2,N3,M1,M2,M3:Integer;MaxErr,FreeHeight:Real;var List:TStringList);
begin
Label1.Caption:='Found configurations: '+IntToStr(List.Count);
Application.ProcessMessages;
if (FreeHeight>=H1) AND (N1<=M1)
then PlaceNext(H1,H2,H3,N1+1,N2,N3,M1,M2,M3,MaxErr,FreeHeight-H1,List)
else
if FreeHeight<=MaxErr
if (FreeHeight>=H2) AND (N2<=M2)
then PlaceNext(H1,H2,H3,N1,N2+1,N3,M1,M2,M3,MaxErr,FreeHeight-H2,List)
else
if FreeHeight<=MaxErr
if (FreeHeight>=H3) AND (N3<=M3)
then PlaceNext(H1,H2,H3,N1,N2,N3+1,M1,M2,M3,MaxErr,FreeHeight-H3,List)
else
if FreeHeight<=MaxErr
end;

procedure TForm1.SpeedButton1Click(Sender: TObject);
var S:TStringList;
begin
S:=TStringList.Create;
ListBox1.Clear;
PlaceNext(55,33,11,0,0,0,10,10,10,2,200,S);
ListBox1.Items:=S;
Label1.Caption:='Found configurations: '+IntToStr(ListBox1.Items.Count);
S.Free;
end;

end.

---------cut here------------

Enjoy!

Jo.
0

Author Comment

ID: 2361373
Hi Jo,

Thanx very much for your time. But something confused me:

1. if I change the initial values of N1,N2,N3 from 0,0,0 to 0,1,1(each of them must be picked at least once) in calling of
PlaceNext(55,30,10,0,0,0,10,10,10,0,100,S)
to
PlaceNext(55,30,10,0,1,1,10,10,10,0,100,S) ,the results are not correct.

2. duplicated results.

Would you so kind to spend more time?
0

LVL 1

Expert Comment

ID: 2362034
Hi zxw,
>1. You MUST set N1,N2,N3 to 0 at the first call. They are used to pass number of already placed boxes to next recursive call. At the time of first call, you have none placed boxes yet. If you do not want results containing zeroes, you can simply add another checks in statements
"if FreeHeight<=MaxErr ..."
like this:
"if (FreeHeight<=MaxErr)
AND(N1>0)
AND(N2>0)
AND(N3>0)..."

>2. This is another question :-). Anyway, having a relatively small list of results, you can filter them in a way you wish.

The procedure PlaceNext can be made in better way:

procedure TForm1.PlaceNext(H1,H2,H3:Real;N1,N2,N3,M1,M2,M3:Integer;MaxErr,FreeHeight:Real;var List:TStringList);
var S:String;
begin
S:=IntToStr(N1)+'/'+IntToStr(N2)+'/'+IntToStr(N3)+' : '+FloatToStr(FreeHeight);
if (FreeHeight<=MaxErr)AND(N1>0)AND(N2>0)AND(N3>0)AND(List.IndexOf(S)<0)
Label1.Caption:='Found configurations: '+IntToStr(List.Count);
Application.ProcessMessages;

if (FreeHeight>=H1) AND (N1<=M1)
then PlaceNext(H1,H2,H3,N1+1,N2,N3,M1,M2,M3,MaxErr,FreeHeight-H1,List);
if (FreeHeight>=H2) AND (N2<=M2)
then PlaceNext(H1,H2,H3,N1,N2+1,N3,M1,M2,M3,MaxErr,FreeHeight-H2,List);
if (FreeHeight>=H3) AND (N3<=M3)
then PlaceNext(H1,H2,H3,N1,N2,N3+1,M1,M2,M3,MaxErr,FreeHeight-H3,List);
end;

This way of filtering doesn't seems to me very elegant, so I'll think around it. There must be another way to avoid results duplicating.

From the other side - this is OBJECT-oriented programming, we have Delphi objects so why not use them ;-))).

Jo.
0

Author Comment

ID: 2365583
Hi Jo,

As mentioned as 2, I then have another question:

I don't think the recursion code runs fast than my code, do you?
0

LVL 1

Accepted Solution

Fatman121898 earned 300 total points
ID: 2365932
Yes I do.

The recursion is a FULL decision of the problem. I mean: if your code places boxes in a given order, let say: on the bottom is placed the big (the first kind of boxes), then smaller (2-nd kind) and at last - smallest boxes (3-rd kind), the recursion finds ALL (I mean it) possible configurations of boxes iun all possible orders they can be placed one over another.
Let say we have three kinds of boxes having size such that one of successfull combinations contains one box of each kind. In this case your code would give one combination such this:

..
o
O

Recursion would give all 6 possible combinations of these three kinds:

.. o o O O O
o . O o . o
O O . . o .

You can check this using the code I posted.

So, in your case this may not be so important, but in real life it has big meaning what is the order of placing boxes or another physical objects.

A couple of months I had a problem writing program wich places some number of rectangles on a big rectangle array in such way that small rectangles occupied as small array as possible. This problem occurs every time when furniture maker have to cut parts ot a big sheet of material in order to minimize cut-offs. Such problem have glass-cutters etc. I did my program using recursion and did it well.

Jo.
0

Author Comment

ID: 2369365
Jo,

0

LVL 1

Expert Comment

ID: 2369807
OK, that's why I posted it to you :-).
Bye.
0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.