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

今回のお題はこちら

重さと価値を入れ替えるというのが思いつきませんでした。。

W = [2,1,3,2] #input
V = [3,2,4,2] #input
maxWeight = 5 #input
MaxV = 100
MaxN = 100
INF = 2**29

$dp = Array.new( W.length + 1 ).map!{ Array.new( MaxV * MaxN + 1, INF ) }
$dp[0][0] = 0
for i in 0..(W.length - 1)
  for v in 0..(MaxV * MaxN)
    if v < V[i] then $dp[i + 1][v] = $dp[i][v]
    else $dp[i + 1][v] = [$dp[i][v], $dp[i][v - V[i]] + W[i]].min
    end
  end
end

ans = 0
for i in 0..(MaxV * MaxN )
  ans = i if $dp[-1][i] <= maxWeight
end
puts ans