はじめに
AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
今回のお題
AtCoder Educational DP Contest - D - Knapsack 1
Difficulty: ---
今回のテーマ、動的計画法
以前の投稿 Ruby の Hash における keys.each と each_key の違い では、ハッシュや配列にマーク代わりとして1を代入していましたが、ナップサック問題は重さ(weight)と価値(value)の二次元になりますので、価値を代入していきます。
Array コピー
ruby.rb
n, mw = gets.split.map(&:to_i)
p = n.times.map { gets.split.map(&:to_i) }
dp = Array.new(mw + 1, 0)
p.each do |w, v|
dp_tmp = dp.dup
w.upto(mw) do |i|
dp_tmp[i] = dp[i - w] + v if dp[i] < dp[i - w] + v
end
dp = dp_tmp
end
puts dp[mw]
insert.rb
dp_tmp[i] = dp[i - w] + v if dp[i] < dp[i - w] + v
1の代わりに、価値を代入しています。
Array 後ろから
ruby.rb
n, mw = gets.split.map(&:to_i)
p = n.times.map { gets.split.map(&:to_i) }
dp = Array.new(mw + 1, 0)
p.each do |w, v|
mw.downto(w) do |i|
dp[i] = dp[i - w] + v if dp[i] < dp[i - w] + v
end
end
puts dp[mw]
詳しい内容は、けんちょんさんの ナップサック DP を in-place 化 ここら辺を参照願います。
Hash版もトライしたのですが、うまくいかなかったです。
Hash （追記）
Hash
n, w = gets.split.map(&:to_i)
wv = Array.new(n){ [0, 0] }
n.times do |i|
wv[i][0], wv[i][1] = gets.split.map(&:to_i)
end
dp = Hash.new(0)
dp[0] = 0
wv.sort_by{ |wv| [wv[0], wv[1]] }.each do |wv|
dp.keys.sort.reverse.each do |k|
if k + wv[0] <= w && dp[k + wv[0]] < dp[k] + wv[1]
dp[k + wv[0]] = dp[k] + wv[1]
end
end
end
puts dp.values.max
| Array コピー | Array 後ろから | Hash | |
|---|---|---|---|
| コード長 (Byte) | 257 | 221 | 375 |
| 実行時間 (ms) | 852 | 864 | 1514 |
| メモリ (KB) | 75024 | 15044 | 108348 |
まとめ
- D - Knapsack 1 を解いた
- Ruby に詳しくなった