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

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Educational DP Contest - E - Knapsack 2
Difficulty: ---

今回のテーマ、動的計画法

前回の投稿 Ruby で解く AtCoder Educational DP Contest D ナップサック問題 と同じ感じなのですが、同じコードですとRE(Runtime Error) になりますので、工夫が必要です。

前回のコード - RE

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]

runtime.error

array size too big (ArgumentError)

Array コピー

ruby.rb

n, mw = gets.split.map(&:to_i)
wv = n.times.map { gets.split.map(&:to_i) }
dp = Array.new(wv.map { _2 }.sum + 1, 10**10)
dp[0] = 0
wv.sort.each do |w, v|
  dp_tmp = dp.dup
  v.upto(dp.size) do |i|
    next if dp[i - v] > mw
    dp_tmp[i] = dp[i - v] + w if dp[i] > dp[i - v] + w
  end
  dp = dp_tmp
end
vmax = 0
dp.each_with_index do |w, v|
  vmax = v if vmax < v && w <= mw
end
puts vmax

dp.rb

    dp_tmp[i] = dp[i - w] + v if dp[i] < dp[i - w] + v # 前回
    dp_tmp[i] = dp[i - v] + w if dp[i] > dp[i - v] + w # 今回

前回と今回で、wとvを入れ替えていることが分かります。
この工夫で、ArgumentError を回避しています。

init.rb

dp = Array.new(mw + 1, 0) # 前回
dp = Array.new(wv.map { _2 }.sum + 1, 10**10) # 今回
dp[0] = 0

wとvを入れ替えるために、前回0で初期化していたところを十分大きな数に変更しています。

Array 後ろから

ruby.rb

n, mw = gets.split.map(&:to_i)
wv = n.times.map { gets.split.map(&:to_i) }
dp = Array.new(wv.map { _2 }.sum + 1, 10**10)
dp[0] = 0
wv.sort.each do |w, v|
  dp.size.downto(v) do |i|
    next if dp[i - v] > mw
    dp[i] = dp[i - v] + w if dp[i] > dp[i - v] + w
  end
end
vmax = 0
dp.each_with_index do |w, v|
  vmax = v if vmax < v && w <= mw
end
puts vmax

inf.rb

dp = Array.new(wv.map { _2 }.sum + 1, Float::INFINITY)
dp = Array.new(wv.map { _2 }.sum + 1, 10**10)

Rubyで大きな数といえばFloat::INFINITYですが、Float::INFINITY は浮動小数点数であるため、整数と浮動小数点数の比較にコストがかかるため、10**10 のような大きな整数を使用しています。

この高速化は、Ruby競プロTips(基本・罠・高速化108 2.7x2.7) を参照しました。

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(1000000001)
dp[0] = 0
wv.sort_by{ |wv| [wv[1], wv[0]] }.each do |wv|
  dp.keys.sort.reverse.each do |k|
    if dp[k + wv[1]] > dp[k] + wv[0] && dp[k] + wv[0] <= w
      dp[k + wv[1]] = dp[k] + wv[0]
    end
  end
end
puts dp.select{ |_, v| v <= w }.sort_by{ |k, v| [-k, v]}[0][0]

	Array コピー	Array 後ろから	Array コピー(INFINITY)	Array 後ろから(INFINITY)	Hash
コード長 (Byte)	406	370	415	379	432
実行時間 (ms)	581	528	710	680	584
メモリ (KB)	74712	15032	74768	15104	60176

上記高速化で150msほど早くなっています。

まとめ

• D - Knapsack 2 を解いた
• @universato さんありがとうございました
• Ruby に詳しくなった