Newsgroups: comp.lang.pascal
Path: utzoo!utgpu!watserv1!watmath!nmouawad
From: nmouawad@watmath.waterloo.edu (Naji Mouawad)
Subject: Re: Fitting files on disk
Message-ID: <1991Mar15.175828.678@watmath.waterloo.edu>
Organization: University of Waterloo
References: <26272@adm.brl.mil>
Date: Fri, 15 Mar 1991 17:58:28 GMT
Lines: 56

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


This is the well know Knapsack problem, where you are given
a knapsack and a set of different weights and you are asked to
fit in the knapsack as much weights as possible.

It is an NP-complete problem. Meaning that the best known
algorithm will run in time exponential in the number of weights.

If you really want to write such a program, your best
bet is dynamic programing, were you built a table to 
solve the problem for a set of increasing knapsacks using
earlier solutions to construct the current one.

Having said that, your intuitive algorithm may give
you on average a solution that differs from the optimal
one by a constant. I suggest that you stick to it, unless
you really want to squeeze the last byte out of your diskettes.

--Naji.

References:
  -Garey and Johnson: Computers and Intractability
   A guide to the Theory of NP-Completness, Freeman.

  -Aho Hopcroft and Ullman, Data Structures and Algorithms,
   Addison-Wesley.
-- 
     -------------------------------------------------------------------
    | Naji Mouawad  |          nmouawad@watmath.waterloo.edu            |
    |  University   |---------------------------------------------------|
    | Of Waterloo   |   "The Stranger in us is our most familiar Self"  |