Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac,att!emory!wuarchive!waikato.ac.nz!canterbury!phys169
From: phys169@csc.canterbury.ac.nz
Newsgroups: comp.lang.pascal
Subject: Re: Fitting files on disk
Message-ID: <1991Mar19.161949.261@csc.canterbury.ac.nz>
Date: 19 Mar 91 04:51:00 GMT
References: <26272@adm.brl.mil>
Organization: University of Canterbury, Christchurch, New Zealand
Lines: 28

In article <26272@adm.brl.mil>, NORM%IONAACAD.BITNET@cunyvm.cuny.edu ( Norman Walsh) writes:
> 
> 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?

As others have said, this can take a long time to solve. I have got a program
to do exactly this, and you should be able to get it via anonymous ftp to
cantva.canterbury.ac.nz [132.181.30.3] in the pc subdirectory. It outputs a
series of COPY and PAUSE commands to the standard output, and has various
levels of optimisation. Sorry, the source isn't available at the moment.
> 
> 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. 

That's what my program does with level zero optimisation does. The default 
level (2) of optimisation usually takes a bit longer (varies a lot with the data,
but 50% longer is typical), i.e. not as long as the brute-force method but often
enough it is better than your (DFF) method.  

There is little benefit in putting too much computational effort into finding
the optimum; you might only save one diskette. What is worth doing is using
a backup program that can split files across diskettes.  I notice that the
PKZIP file format specifications allow for multiple-volume backups, and wonder
why this hasn't been implemented yet. 

Mark Aitchison, Physics, University of Canterbury, New Zealand.