ナップサック問題

今日は、RubyのStructクラスの練習をかねてナップサック問題に取り組んでみました。

品物の大きさと価値は、以下のようになっています。

品　物	0	1	2	3	4
大きさ	2	3	5	7	9
価　値	2	4	7	11	14

knapsack.rb

Item = Struct.new(:weight, :value)

def knapsack(items, total, choice)
  items.length.times do |i| 
    items[i].weight.step(total.length-1) do |j| 
      v = total[j-items[i].weight] + items[i].value
      if v > total[j] 
        total[j] = v 
        choice[j] = i
      end
    end 
  end 
end 

def display(items, total, choice, m)
  print "\tMax Value = #{total[m]} ( "
  loop do 
    print "#{items[choice[m]].value}"
    m -= items[choice[m]].weight
    break if m == 0
    print " + "
  end
  puts " )"
end

if __FILE__ == $0
  items = [ Item.new( 2, 2),
            Item.new( 3, 4),
            Item.new( 5, 7),
            Item.new( 7,11),
            Item.new( 9,14) ]
  print "Input knapsack size? => "
  m = gets.to_i

  total  = Array.new(m + 1, 0) 
  choice = Array.new(m + 1, -1)

  knapsack(items, total, choice)
  display(items, total, choice, m)
end

実行結果

mmasa@debian:~/work/ruby$ ruby knapsack.rb
Input knapsack size? => 10
        Max Value = 15 ( 11 + 4 )
mmasa@debian:~/work/ruby$ ruby knapsack.rb
Input knapsack size? => 15
        Max Value = 22 ( 11 + 7 + 4 )
mmasa@debian:~/work/ruby$ ruby knapsack.rb
Input knapsack size? => 20
        Max Value = 30 ( 11 + 11 + 4 + 4 )