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

前回のお題を再帰を使わずループを使って書き直してみました。
こっちの方がわかりやすいですな。

W = [2,1,3,2] #input
V = [3,2,4,2] #input
maxWeight = 5 #input

$dp = Array.new( W.length ).map!{ Array.new( maxWeight + 1, 0 ) }
(W.length - 1).downto(0) do |i|
  for w in 0..maxWeight
    if i == W.length - 1 then $dp[i][w] = 0
    elsif w < W[i] then $dp[i][w] = $dp[i + 1][w]
    else $dp[i][w] = [$dp[i + 1][w], $dp[i + 1][w - W[i]] + V[i]].max
    end
  end
end

puts $dp[0][maxWeight]