プログラミングコンテストチャレンジブック演習「ナップサック問題」

今回のお題はこちら。

今回はdp用メモテーブル$dpのサイズを間違えて不具合になりました。
ナップサックに入れられる重さは0〜wなので、
配列のサイズはwじゃなくてw+1にしないといけないんですなー。

W = [2,1,3,2] #input
V = [3,2,4,2] #input
w = 5 #input
INF = -1

$dp = Array.new( W.length ).map!{ Array.new( w + 1, INF ) }
def maxValue(index, leftWeight)
  return $dp[index][leftWeight] unless $dp[index][leftWeight] == INF
  value = 0
  if index == W.length - 1
    value = 0
  elsif W[index] <= leftWeight
    value = [maxValue(index + 1, leftWeight), maxValue(index + 1, leftWeight - W[index]) + V[index]].max
  else
    value = maxValue(index + 1, leftWeight)
  end
  $dp[index][leftWeight] = value
  return value
end

puts maxValue(0, w)