Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!usc!apple!vsi1!zorch!xanthian From: xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) Newsgroups: comp.sources.d Subject: Re: v15i083: Awk program for putting a set of files on minimum floppies. Message-ID: <1990Dec17.063920.28799@zorch.SF-Bay.ORG> Date: 17 Dec 90 06:39:20 GMT References: <114639@uunet.UU.NET> Organization: SF-Bay Public-Access Unix Lines: 30 In comp.sources.misc thomas%randvax.UUCP@usc.edu (Susan Thomas) writes: >Archive-name: greedy/part01 >(I'm posting this for a friend) >This is a awk implementation of the "greedy" bin-packing algorithm >as applied to the problem of spreading a set of files over a set >of floppies in such a way as to require the least number of >floppies. It takes a list of files and generates copying scripts >which embody the optimal allocation of files. >Greedy is not the optimal algorithm. It's just a easily implemented >heuristic. If in fact this works well, it would be nice if someone adapted it into a version of shar to pack the pieces of a shar into the fewest, say 60Kbyte, articles possible, to save header and archive bytes. Diskettes aren't the only place where efficient packing is useful! [For shars of directory trees, this would require a smarter shar, that created all needed directories first, and handed current-directory-relative file pathnames to sed rather than doing a cd to the directory, and it would force one to unpack at least the first part of a multipart shar before the other parts. Is this too much of a sacrifice? Of course, for a shar of one flat directory, there would be nothing given away, just gain.] Kent, the man from xanth.