ナップサック問題その2

knapsack2.rb

## ナップサック問題その2
## http://rubyfiddle.com/riddles/5c02c

n = 4
w = [2,1,3,2]
v = [3,2,4,2]
W = 5

res =0
INF = 1000000

dp = Array.new(n+1,INF).map{Array.new(n*n+1,INF)}
j=0
dp[0][0] = 0

n.times{|i|
  (n*n).times {|j|
    if  j < v[i]
      dp[i+1][j] = dp[i][j]
    else
      dp[i+1][j] = [dp[i][j] , dp[i][j-v[i]]+w[i]].min
    end
    }
  }
i = 0
while i <= n*n
  if dp[n][i] <= W
    res = i
  end
  i += 1
end

puts res