Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!samsung!uunet!microsoft!t-rayc
From: t-rayc@microsoft.UUCP (Raymond CHEN)
Newsgroups: comp.lang.pascal
Subject: Re: (R)Program to put a set of files on as few floppies a.p.
Message-ID: <56855@microsoft.UUCP>
Date: 23 Aug 90 16:02:45 GMT
References: <24244@adm.BRL.MIL>
Reply-To: t-rayc@microsoft.UUCP (Raymond CHEN)
Organization: Microsoft Corp., Redmond WA
Lines: 29

In article <24244@adm.BRL.MIL> CDCKAB%EMUVM1.BITNET@cunyvm.cuny.edu ( Karl Brendel) writes:
>I don't have any disagreement with your underlying algorithm, which
>appears to be simply
>
>        while files remain unpicked
>          pick the largest file that fits on the diskette
>
>Not having any knowledge of dynamic programming, my "intuition" had long
>ago led to the same conclusion, as many other people's must have led
>them. (That probably means we're all wrong together. ;))

Consider the following file sizes for a disk that can hold 10 units

	6 5 3 2 2 2

the greedy algorithm (described above) yields

	Disk 1: 6+3
	Disk 2: 5+2+2
	Disk 3: 2

whereas the optimal packing would be

	Disk 1: 6+2+2
	Disk 2: 5+3+2


So although the "obvious" algorithm tends to do a good job, it doesn't
always do the *best* job.