# An algorithm to deposit boxes

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;
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Author Commented:
0
Commented:
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 Commented:
Mr. fatman,

You can see now how patient I am waiting and how eager I am to see you again!
0
Author Commented:
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
Commented:
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 Commented:
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
Commented:
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 Commented:
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
Commented:
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

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:
Jo,