R1TMARG%AKRONVM@vm1.cc.uakron.edu ( Tim Margush) (03/15/91)
>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? ... >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) This problem is a form of the "bin packing problem" The Bin-Packing problem asks you to find the least number of bins into which n objects with positive integer weights can be placed. Each bin may contain a total weight of at most M. It is assumed that no weight is greater than M. This problem is NP-complete... meaning that there is no "reasonable" algorithm to always produce the optimum result. Brute force would work, but even for modest sized problems, the number of possibilities is enormous. If you are willing to settle for a fast solution that is not always optimal, the strategy you suggested is usually employed. First sort the files by decreasing length and then place each file on the first disk with sufficient room. This approach is called "Decreasing First Fit." Unfortunately, this will sometimes give a non-optimal result. eg. file sizes: 4, 3, 2, 2, 2 disk size: 8 DFF OPTIMAL disk 1 4 3 4 2 2 disk 2 3 2 2 3 3 2 disk 3 2 not required For the application mentioned, you will seldom run across instances where the DFF algorithm does not produce the optimal solution. Even if it does, one extra disk is usually all that is required. --------------------------------------------------------------------- Tim Margush R1TMARG@AKRONVM.BITNET Department of Mathematical Sciences R1TMARG@VM1.CC.UAKRON.EDU University Of Akron R1TMARG@AKRONVM.UAKRON.EDU Akron, OH 44325 (216) 972-7109