ナップサック問題

重さと価値がそれぞれwi,viであるようなn個の品物があります。
これらの品物から、重さの総和がWを超えないように選んだ時の価値の総和の
最大値を求めなさい。


# 再帰呼び出し

N = 4
ARRAY = [ [2, 3], [1, 2], [3, 4], [2, 2] ]
ARRAY_W = [ 2, 1, 3, 2 ]
ARRAY_V = [ 3, 2, 4, 2 ]
W = 5

def rec(i, j)
  res = 0
  if i == N
    # もう品物は残っていない
    res = 0
  elsif j < ARRAY_W[i]
    #この品物は入らない
    res = rec(i + 1, j)
  else
    #入れない場合と入れる場合の両方を試す
    res = [ rec(i + 1, j), rec(i + 1, j - ARRAY_W[i]) + ARRAY_V[i] ].max
  end
  res
end

puts "#{rec(0, W)}"


# 再帰呼び出し(メモ化)


def rec_memo(i, j, memo_arr)
  if memo_arr[i][j] >= 0
    memo_arr[i][j]
  end

  if i == N
    res = 0
  elsif j < ARRAY_W[i]
    res = rec_memo(i + 1, j, memo_arr)
  else # ARRAY_W[i] < j
    res = [ rec_memo(i + 1, j, memo_arr), rec_memo(i + 1, j - ARRAY_W[i], memo_arr) + ARRAY_V[i] ].max
  end
  memo_arr[i][j] = res
end

memo_arr = Array.new(W + 1, Array.new(W + 1, -1))

p "#{rec_memo(0, W, memo_arr)}"

# 動的計画法

N = gets.to_i
W = gets.to_i

arr_w = []
arr_v = []

N.times do |i|
  key, value = gets.split(" ").map(&:to_i)
  arr_w << key
  arr_v << value
end

max_cost = 0
dp = Hash.new
dp[0] = 0

N.times do |ind|
  dp_tmp = dp.clone

  dp.each do |key, value|
    total_key = key + arr_w[ind]
    total_value = value + arr_v[ind]

    unless dp_tmp.has_key?(total_key)
      dp_tmp[total_key] = total_value
    end

    if W >= total_key && total_value > max_cost
      max_cost = total_value
    end
  end

  dp = dp_tmp
end

p max_cost