Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!uunet!comp.vuw.ac.nz!matai.vuw.ac.nz!forbesmc
From: forbesmc@matai.vuw.ac.nz
Newsgroups: comp.lang.pascal
Subject: Re: Fitting files on disk
Message-ID: <1991Mar15.091754.344@matai.vuw.ac.nz>
Date: 14 Mar 91 21:17:54 GMT
References: <26272@adm.brl.mil>
Organization: Victoria University of Wellington,  NZ
Lines: 40

In article <26272@adm.brl.mil>, NORM%IONAACAD.BITNET@cunyvm.cuny.edu ( Norman Walsh) writes:
> Hello,
> 
> I have a question that I cannot answer sufficiently for myself:
> 
> Given a collection of n files (.zip files in my case) is there an
> algorithm (short of brute-force) for determining the best arrangement
> of files to fit on as few disks (of a given size) as possible?
> 
> Suppose, for example, I have 40 files that range in size from 30 to
> 400 kb.  I want to move them all to floppies but I want to do so in
> such a way as to use as few floppies as possible.  I want each file to
> be complete on one disk, i.e. I don't want to split files across
> disks.
> 
> My first-guess algorithm is to always place the largest file that will
> fit on a particular disk on that disk.  However, I have my suspicions
> that this is not the gauranteed best way of doing it.  Unfortunately,
> I can't think of a better way nor can I demonstrate mathematically that
> the biggest-first algorthim is the best...(or not)
> 
> Any thoughts?
> 
>                                                   ndw
I think your first guess is right : have a list of the files in order
of descending size, pick the largest file and write to the disk, 
find out how much space is left on the disk and put the largest
remaining file that will fit onto it.  Repeat until no more files
will fit on the disk.  Now repeat the entire procedure for the 
next disk etc.  (this method is used to minimise the queuing time
for printers etc so should work for minimising the number of disks).

-- 
+------------------------------------------------------------------+
| I'm a toxophilite,         | Murray Forbes,                      |
| so what's your problem?    | Physics Department,                 |
|----------------------------| Victoria University of Wellington,  |
| standard disclaimer :      | New Zealand.                        |
| all opinions here are mine | FORBESMC@MATAI.VUW.AC.NZ            |
+------------------------------------------------------------------+