Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!usc!samsung!think!sdd.hp.com!uakari.primate.wisc.edu!aplcen!haven!adm!news
From: CDCKAB%EMUVM1.BITNET@cunyvm.cuny.edu ( Karl Brendel)
Newsgroups: comp.lang.pascal
Subject: (R)Program to put a set of files on as few floppies a.p.
Message-ID: <24244@adm.BRL.MIL>
Date: 21 Aug 90 14:27:06 GMT
Sender: news@adm.BRL.MIL
Lines: 103


Ajay Shah <ajayshah@aludra.usc.edu> writes

>This program takes on StdIn a list of file names and sizes.

>the number of floppies he'll need.  I believe the algorithm used
>guarantees that there is no alternative layout of files over
>floppies which could consume fewer floppies.  Tell me if i'm
>wrong!.  (My intuitive justification uses the analogy between
>this algorithm and dynamic programming).

>        function find(max:longint):integer;
>        type
>                Candidate = record
>                        index : 1..MaxFiles;
>                        size : longint
>                end;
>        var
>                C: array[1..MaxFiles] of Candidate;
>                i, num : integer;
>                tmpC : Candidate;
>                nochange : boolean;
>        begin
>                num := 0;
>                for i := 1 to N do
>                        if not flist[i].taken then
>                                if flist[i].fsize <= max then
>                                begin
>                                        inc(num);
>                                        C[num].index := i;
>                                        C[num].size := flist[i].fsize
>                                end;
>
>                if num = 0 then {no file small enough found.}
>                begin
>                        find := 0; exit
>                end;
>
>                {Now bubblesort C}
>                repeat
>                        nochange := true;
>                        for i := 1 to num-1 do
>                                if C[i].size > C[i+1].size then
>                                begin
>                                        tmpC := C[i];
>                                        C[i] := C[i+1];
>                                        C[i+1] := C[i];
>                                        nochange := false
>                                end;
>                until nochange;
>                find := C[num].index {index of largest file of list}
>        end;


I don't have any disagreement with your underlying algorithm, which
appears to be simply

        while files remain unpicked
          pick the largest file that fits on the diskette

Not having any knowledge of dynamic programming, my "intuition" had long
ago led to the same conclusion, as many other people's must have led
them. (That probably means we're all wrong together. ;))

What I _do_ want to ask is: Why do you write function find in such a
complex manner, requiring a sort of your C array, when it would appear
sufficient to write something like this:

fuction find(max : longint) : integer;
var
  smax : longint;
begin {find}
  num := 0;
  smax := 0;
  for i := 1 to N do
    if not flist[i].taken then
      if flist[i].fsize <= max then
        if flist[i].fsize > smax then
        begin {new max}
          num := i;
          smax := flist[i].fsize;
        end; {new max}
   find := num;
end; {find}

I'm mailing other remarks directly to you because they may be of less
general interest than implementation of your fundamental algorithm. If
you disagree (about the general interest), feel free to reply here or
post my remarks--or I will if requested by other readers.

Oh: one item of general interest to those who will attempt to use your
code as posted: In the bubble sort, "C[i+1] := C[i];" should be "C[i+1]
:= tmpC;". As written, the sort leads to an list where the largest
fitting file is not always the next chosen.

Thank you for provoking some thought early in the morning. <smile>

Karl Brendel
Centers for Disease Control
Epidemiology Program Office               Home of Epi Info 5.0
Atlanta, GA
phone 404/639-2709
fts       236-2709