knapsack ruby

knapsack.rb

W = 10
v = [17, 1, 5, 15, 9, 2, 10, 8, 5, 16, 3, 17, 3, 3, 18, 12, 18, 20, 18, 8]
w = [5,  1, 4,  3, 4, 2, 1,  3, 2, 5,  3, 4,  1, 5,  2,  4,  5,  2,  3, 5]
n = v.size
m = Array.new(n + 1){ Array.new(W, 0) }

n.times do |i|
  W.times do |j|
    m[i + 1][j] =
      if j + 1 < w[i]
        m[i][j]
      elsif j >= w[i]
        [m[i][j], m[i][j - w[i]] + v[i]].max
      else
        [m[i][j], v[i]].max
      end
  end
end

puts m.map(&:inspect)
puts m[n][W - 1]