Ruby で解く AtCoder Educational DP Contest D ナップサック問題

はじめに

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 に詳しくなった