Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!umriscc!mcs213e.cs.umr.edu!mcastle
From: mcastle@mcs213e.cs.umr.edu (Mike Castle {Nexus})
Newsgroups: comp.lang.pascal
Subject: Re: Fitting files on disk
Message-ID: <2406@umriscc.isc.umr.edu>
Date: 15 Mar 91 02:49:03 GMT
References: <26272@adm.brl.mil>
Sender: news@umriscc.isc.umr.edu
Organization: University of Missouri - Rolla
Lines: 28

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

Amazingly enough, I happen to have to do a program that does something
very similiar to this (puttint objects into backpacks) for my data
structures class.  Of course, I haven't started on it yet.

Starting off with the biggest file IS one method (a heuristic method, as my
prof said).  The method we have to use will be to go through all the possible
packing combinations, reporting which one will work (well, we stop tracing a
method back once it becomes apparent that that combination wont work).  I
believe the complexity of O(n^2) once you apply dynamic programming in addition
to the divide and conquer method, but I'm not sure (too lazy to look it up
in my notes :-).  Maybe when I get done with that program, I'll upload the
generic code to simtel and garbo.  

Interesting.
-- 
Mike Castle (Nexus) S087891@UMRVMA.UMR.EDU (preferred)       | XEDIT: Emacs
                mcastle@mcs213k.cs.umr.edu (unix mail-YEACH!)| on a REAL
Life is like a clock:  You can work constantly, and be right | operating
all the time, or not work at all, and be right twice a day.  | system. :->