1. sorting blocks in 1 unit , the program
- Posted by =?iso-8859-2?B?qWtvZGE=?= <tone.skoda at SIOL.NET> Apr 07, 2000
- 401 views
- Last edited Apr 08, 2000
------=_NextPart_000_003D_01BFA0D1.89DC7A00 charset="iso-8859-2" Content-Transfer-Encoding: quoted-printable 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. ------=_NextPart_000_003D_01BFA0D1.89DC7A00 charset="iso-8859-2" Content-Transfer-Encoding: quoted-printable <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content=3D"text/html; charset=3Diso-8859-2" = http-equiv=3DContent-Type> <META content=3D"MSHTML 5.00.2614.3401" name=3DGENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=3D#ffffff> <DIV><FONT face=3DArial size=3D2>anybody written or knows of program = which sorts=20 blocks of different size in 1 unit so that this unit is maximally=20 used.</FONT></DIV> <DIV> </DIV> <DIV><FONT face=3DArial size=3D2>I have many games of different sizes=20 (150MB,300MB...)which I want to copy to CD which has size 650 MB. I want = the=20 space on CD to be maximally used.</FONT></DIV> <DIV><FONT face=3DArial size=3D2>anybody smart enough to write it for=20 me?</FONT></DIV> <DIV><FONT face=3DArial size=3D2>I know it's quite simple algorithm. you = have to=20 ------=_NextPart_000_003D_01BFA0D1.89DC7A00--
2. Re: sorting blocks in 1 unit , the program
- Posted by Pete Eberlein <xseal at HARBORSIDE.COM> Apr 07, 2000
- 423 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
3. Re: sorting blocks in 1 unit , the program
- Posted by =?iso-8859-2?B?qWtvZGE=?= <tone.skoda at SIOL.NET> Apr 07, 2000
- 390 views
- Last edited Apr 08, 2000
Thanks Pete for code. It works great, just what i needed. You're a genious! Did you write it now or did you have it already before? Here is my verison , just litle code added, to be more user friendly: ------------------------------------------- function sum(sequence s) atom ret ret=0 for i=1 to length(s) do ret+=s[i] end for return ret end function 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 printf(1,"%s%d%s%d%s",{"sum=",sum(temp),", left space=",boxsize-sum(temp),"\n\n"}) 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") pack_boxes({100,70,300,60,3,255,150,100,200,350,270}, 650) puts(1, "\n") ---------------------------------------------