OpenEuphoria

2. Re: sorting blocks in 1 unit , the program

• Posted by Pete Eberlein <xseal at HARBORSIDE.COM> Apr 07, 2000
• 638 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