ナップサック問題

knapsack.rb

## ナップサック問題
## http://rubyfiddle.com/riddles/5deb1

# 品物の大きさ
$w = [2, 1, 3, 2]
# 品物の価値
$v = [3, 2, 4, 2]
N = $w.size
# ナップサックの容量
W=5

# メモ化テーブル
$dp = Array.new(N+1,-1).map{|i|Array.new(W+1,-1)}

def rec(i, j)
  
  #すでに調べた値だった場合、その値を返す
  return $dp[i][j] if $dp[i][j] >= 0

  # もう品物が残っていない場合
  if i == N
    res = 0
  # 品物がナップサックの容量より大きい場合
  elsif j < $w[i]
    # 次の品物を調べる
    res = rec(i+1,j)
  # 品物が残っていて、ナップサックに入る場合
  else
    # 品物を入れない場合と入れる場合で価値が大きい方を調べる
    res = [rec(i+1,j), rec(i+1, j-$w[i])+$v[i]].max
  end

  # 結果をメモ化テーブルに記憶する
  return $dp[i][j] = res
end

puts rec(0,W)