（備忘録）問題解決のための「アルゴリズム数学」〜 8

問題

atcoder.jp

自分の回答

書籍に書いてある回答の手引き見て内容理解しててもいざ実装すると難しい。。。 これも他の方の回答見て参考にしています

N,W = gets.split.map(&:to_i)

# 入力を格納する配列
WN = Array.new

N.times do
  WN << gets.split.map(&:to_i)
end

# 動的計画法
dp = Array.new
dp[0]=Array.new(W+1,0)

# 商品をeach(最後の分は含まない）
(0...N).each do |i|
  dp[i+1] = Array.new
  # 重さをeach
  (0..W).each do |j|
    if j < WN[i][0]
      dp[i+1][j] = dp[i][j] 
    else
      dp[i+1][j] = [dp[i][j], dp[i][j-WN[i][0]]+WN[i][1]].max 
    end
  end
end

puts dp[N].max