Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!csn!boulder!tigger!hampton
From: hampton@tigger.Colorado.EDU (Jeff Hampton)
Newsgroups: comp.lang.pascal
Subject: Re: Fitting files on disk
Summary: Some possible aglgorithms to consider and time complexity.
Message-ID: <1991Mar16.012109.8541@colorado.edu>
Date: 16 Mar 91 01:21:09 GMT
Sender: news@colorado.edu (The Daily Planet)
Organization: University of Colorado, Boulder
Lines: 50
Nntp-Posting-Host: tigger.colorado.edu

Expires:  04/01/91

References: <26272@adm.brl.mil>
Sender: Jeff Hampton

Followup-To: 
Distribution: usa
Organization: University of Colorado, Boulder (dept. of Computer Science)

Keywords: algorithms


I have been thinking of a similar type of problem myself. The problem however is
an NP-complete problem. If you use the strategy of first fit, the worst-case
time complexity is on the order of n^2 and produces good results. Below is an
example algorithm for nonincreasing first fit(taken from Computer Algorithms
by Sara Baase, 2nd ED. p.339)

input: S=(s1,...,sn), where 0<si<=1 for 1<=i<=n
output: An array bin where for 1<=i<=n, bin[i] is the number of the bin into
        which si is placed.

procedure NIFF (S:RealArray;n:integer;var bin:IntegerArray);
var used: array[1..n] of real;
    {used[j] is the amount of space in bin j already used up.}
    i,j:integer;
BEGIN
  {Sort S into nonincreasing order.}
  for j:=1 to n do used[j]:=0 end;
  for i:=1 to n do
    {Look for a bin in which si fits.}
     j:=1;
     while used[j]+si > 1 do j:=j+1;
     bin[i]:=j;
     used[j]:=used[j]+si;
  end; { for }
end. { NIFF }

The sort can be done in n*lg(n), and j is incremented while searching for an
appropriate bin at most n(n-1)/2 times. All the other instructions are executed
at most n times, so the worst-case time complexity is no more than n^2.
The expected number of extra bins is at most roughly 0.3*sqrt(n). Other
strategies include best-fit, and next-fit. Best-fit if the si or sorted in
nonincreasing order, it works about as well as first-fit. Next fit is faster
but will create extra bins. Thus are some things to think about when
considering your problem. I hope this helps somewhat.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Jeff Hampton | email: hampton@tigger.colorado.edu | University of Colorado +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++