Re: sorting blocks in 1 unit , the program
- Posted by Pete Eberlein <xseal at HARBORSIDE.COM> Apr 07, 2000
- 454 views
On Fri, 7 Apr 2000 20:40:41 +0200, =?iso-8859-2?B?qWtvZGE=?= <tone.skoda at SIOL.NET> wrote: >anybody written or knows of program which sorts blocks of different size in 1 unit so that this unit is maximally used. > >I have many games of different sizes (150MB,300MB...)which I want to copy to CD which has size 650 MB. I want the space on CD to be maximally used. >anybody smart enough to write it for me? >I know it's quite simple algorithm. you have to combine all combinations and select the best. > Here's some box packing routines that will probably do the trick. It packs the fewest elements into each box if the items are sorted in ascending order. ------------------------------------------- function pack(sequence items, atom boxsize) atom bestsize, thissize sequence bestitems, temp bestsize = 0 bestitems = {} for i = length(items) to 1 by -1 do if items[i] <= boxsize then temp = pack(items[1..i-1]&items[i+1..length(items)], boxsize-items[i]) thissize = items[i] for j = 1 to length(temp) do thissize += temp[j] end for if thissize > bestsize then bestsize = thissize bestitems = items[i] & temp end if end if end for return bestitems end function procedure pack_boxes(sequence items, integer boxsize) sequence temp integer j while length(items) do temp = pack(items, boxsize) ? temp for i = 1 to length(temp) do j = find(temp[i], items) items = items[1..j-1]&items[j+1..length(items)] end for end while end procedure pack_boxes({2,3}, 4) puts(1, "\n") pack_boxes({2,3,4}, 5) puts(1, "\n") pack_boxes({2,3,4,5}, 5) puts(1, "\n") pack_boxes({3,4,5,6}, 10) puts(1, "\n") pack_boxes({3,4,5,6}, 15) puts(1, "\n") --------------------------------------------- Pete Eberlein