Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!emory!gatech!udel!haven!adm!news
From: NORM%IONAACAD.BITNET@cunyvm.cuny.edu ( Norman Walsh)
Newsgroups: comp.lang.pascal
Subject: Fitting files on disk
Message-ID: <26272@adm.brl.mil>
Date: 14 Mar 91 15:19:33 GMT
Sender: news@adm.brl.mil
Lines: 23

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