查看完整版本: Ruby程序处女作,算法中的最优装载问题

Ruby程序处女作,算法中的最优装载问题

问题描述
有n个集装箱要装上1艘载重量分别为c的轮船，其中第i个集装箱的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船，并找出一种装载方案

其中
@w  #集装箱的重量数组
@c   #货船的最大载重量
@n   #集装箱的个数
@r    #未被装载的货物重量
@cw  #当前货船上的载重
@i     #搜索树的层数
@bestw #最优值
@bestx  #最优解

[code]
class Loading
  def initialize(weight,cont)
    @w,@c,@n=weight,cont,weight.length
    @r,@cw,@i,@bestw=0,0,0,0
    @x=Array.new
    @bestx=Array.new
    for j in 0..@n-1
       @r=@r+@w[j];@bestx[j],@x[j]=0,0
     end
     print "集装箱的总重量为 #@r,\n"
   end
   def MaxLoading
     while true
       while @i<=(@n-1) and (@cw+@w[@i]<@c)
         @r-=@w[@i]
         @cw+=@w[@i]
         @x[@i]=1
         print "在左子树中",@x[@i],"\n"
         @i+=1
       end
       if @i>@n-1
         for j in 0..@n-1
           @bestx[j]=@x[@i]
           print '到达叶子节点',j,"\t @bestx[j]",@bestx[j],"\n"
         end
         @bestw=@cw
       else
         @r-=@w[@i];@x[@i]=0;
         print '在右子树中',@x[@i],"\n"
         @i+=1
       end
      while @cw+@r<=@bestw
         @i-=1
         while @i>=0 and (@x[@i]==0)
           @r+=@w[@i];@i-=1
         end
         if @i==-1 then
           print "@bestw:",@bestw  
           return
         end
         @x[@i]=0
         @cw-=@w[@i]
         @i+=1
       end
     end
   end
end

weight=[30,10,10]
cont=35
s=Loading.new(weight,cont)
s.MaxLoading


[/code]


运行的结果如下:

集装箱的总重量为 50,
在左子树中1
在右子树中0
在右子树中0
到达叶子节点0         @bestx[j]nil
到达叶子节点1         @bestx[j]nil
到达叶子节点2         @bestx[j]nil
@bestw:30>Exit code: 0