Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!swrinde!emory!mephisto!prism!ccoprrm
From: ccoprrm@prism.gatech.EDU (Robert E. Minsk)
Newsgroups: comp.lang.pascal
Subject: Re: (R)Program to put a set of files on as few floppies a.p.
Message-ID: <12853@hydra.gatech.EDU>
Date: 21 Aug 90 22:10:17 GMT
References: <24244@adm.BRL.MIL>
Organization: Office of Computing Service - High Performace Computing
Lines: 33

In article <24244@adm.BRL.MIL> CDCKAB%EMUVM1.BITNET@cunyvm.cuny.edu ( Karl Brendel) writes:
>Ajay Shah <ajayshah@aludra.usc.edu> writes
>
>>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!.

  This problem is better know as the bin packing problem which is in the NP
complete set of problems (i.e. I won't live that long to find the correct
ordering for a reasonable size data set.;-)  To find the minimum number of
disks needed and the correct ordering to write the files, almost all (if not
all) orderings must be tried.

>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

  This algorithm will not give the minimum number of disk but will give a
pretty good answer.  So yup, you were wrong :-).  For more discussion on NP
complete and bin packing (and other such problems) there are several good
papers and books.  One book I remember off the top of my head is "Computer
Algorithms - Introduction to Design and Analysis" by Sara Baase.  If I
remember corectly the number of extra disk (bins) will be aproximately
0.3*sqrt(n) extra disks, but don't quote me on that.  If anyone wants an
example of where the posted algorithm fails please send me mail.

Robert E. Minsk - Office of Computing Services        | Save the whales...    |
ARPA: ccoprrm@prism.gatech.edu                        | Collect the whole set |
uucp: ...!{allegra,amd,hplabs,seismo,ut-ngp}!gatech!prism!ccoprrm
Georgia Institute of Technology, Atlanta Georgia, 30332