(備忘録)問題解決のための「アルゴリズム数学」〜 8
問題
自分の回答
書籍に書いてある回答の手引き見て内容理解しててもいざ実装すると難しい。。。 これも他の方の回答見て参考にしています
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