Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

ナップサック問題

今日は、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 )