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;
             IJKList.Add(I);
             IJKList.Add(J);
             IJKList.Add(K);
        end;
    end;

    {something else}
   
    IJKList.Free;
end;
zxwAsked:
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.

zxwAuthor Commented:
Adjusted points to 100
0
Fatman121898Commented:
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
zxwAuthor Commented:
Mr. fatman,

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

This course will teach participants about installing and configuring Python, syntax, importing, statements, types, strings, booleans, files, lists, tuples, comprehensions, functions, and classes.

zxwAuthor 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;

           //Added Line
           rMin := rTemp;
 
           IJKList.Add(I);
           IJKList.Add(J);
           IJKList.Add(K);
        end;
      end;
0
Fatman121898Commented:
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
          then List.Add(IntToStr(N1)+'/'+IntToStr(N2)+'/'+IntToStr(N3)+' : '+FloatToStr(FreeHeight));
    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
          then List.Add(IntToStr(N1)+'/'+IntToStr(N2)+'/'+IntToStr(N3)+' : '+FloatToStr(FreeHeight));
    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
          then List.Add(IntToStr(N1)+'/'+IntToStr(N2)+'/'+IntToStr(N3)+' : '+FloatToStr(FreeHeight));
   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
zxwAuthor 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
Fatman121898Commented:
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)
      then List.Add(S);
    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
zxwAuthor 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
Fatman121898Commented:
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

Your issues matter to us.

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

Start your 7-day free trial
zxwAuthor Commented:
Jo,

Thanx a lot. And I will adjust your code.
0
Fatman121898Commented:
OK, that's why I posted it to you :-).
Bye.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Delphi

From novice to tech pro — start learning today.