ナップサック問題
個数制限あり
メモ化のやり方
DP遷移式 (漸化式) を立てる
$ \rm{dp}[i+1][w] = \left\{\begin{array}{ll}\max (\rm{dp}[i][w-\rm{weight}[i]] + \rm{value}[i], \rm{dp}[i][w]) & (w \ge \rm{weight}[i]) \\\rm{dp}[i][w] & (w < \rm{weight}[i])\end{array}\right.
初期値を設定する
dp[i]の値から、dp[i+1]を求める
https://qiita-user-contents.imgix.net/https%3A%2F%2Fqiita-image-store.s3.amazonaws.com%2F0%2F182963%2Ffcd3c29a-9f3e-7984-3549-21fa113fab26.jpeg?ixlib=rb-1.2.2&auto=format&gif-q=60&q=75&w=1400&fit=max&s=6e75d6c9665030dd73dcb87ba6b713a2
code:ruby
N,W = gets.split.map(&:to_i)
value = Array.new(N)
weight = Array.new(N)
N.times {|i| valuei, weighti = gets.split.map(&:to_i) } dp = Array.new(N+1) {Array.new(W+1){0}}
(0...N).each do |i|
(0..W).each do |w|
dpi[w-weighti] + valuei, # 品物iを選んだとき ].max # 価値の総和が大きいほうを採用する
else
# w よりも weighti が大きいとき、品物iが選ばれていることはありえない dpi+1w = dpiw # 価値の総和は品物iを選ばなかったときから変化しない end
end
end
個数制限なし
個数制限ありとほとんど変わらない
$ \rm{dp}[i+1][w] = \left\{\begin{array}{ll}\max (\rm{dp}[i+1][w-\rm{weight}[i]] + \rm{value}[i], \rm{dp}[i][w]) & (w \ge \rm{weight}[i]) \\\rm{dp}[i][w] & (w < \rm{weight}[i])\end{array}\right.
品物$ i を選ぶときの候補が $ dp[i+1][w−weight[i]]+value[i] になるだけ
個数制限なしナップサックでは、「品物 i を選ぶ」という遷移によって $ dp[i+1][w] の状態になったとしても、その遷移前も i 番目の品物が入っているかもしれないので「品物 i までから重さ $ w-weight[i] 以下で」になります。
https://qiita-user-contents.imgix.net/https%3A%2F%2Fqiita-image-store.s3.amazonaws.com%2F0%2F182963%2Ffcd3c29a-9f3e-7984-3549-21fa113fab26.jpeg?ixlib=rb-1.2.2&auto=format&gif-q=60&q=75&w=1400&fit=max&s=6e75d6c9665030dd73dcb87ba6b713a2
上記図のように個数制限ありの場合は$ dp[i] のrowを参照するが、$ dp[i+1] (現在更新している対象のrow) を参照できる
$ dp[i+1] のrowに関するloopの中でより多くの更新がなされる
code:ruby
N,W = gets.split.map(&:to_i)
value = Array.new(N)
weight = Array.new(N)
N.times {|i| valuei, weighti = gets.split.map(&:to_i) } dp = Array.new(N+1) {Array.new(W+1){0}}
(0...N).each do |i|
(0..W).each do |w|
# ↓ココが差分
dpi+1[w-weighti] + valuei, # 品物iを選んだとき (dpi+1ですでに選ばれていても構わない) ].max # 価値の総和が大きいほうを採用する
else
# w よりも weighti が大きいとき、品物iが選ばれていることはありえない dpi+1w = dpiw # 価値の総和は品物iを選ばなかったときから変化しない end
end
end
参考