🐸

[鉄則B19] Knapsack 2

2024/03/28に公開

Ruby

ナップサックの応用問題。

問題の要約

価値より大きさの方が大きい場合に高速に計算するには？

自力で考えたもの (RE)

N, W = gets.split.collect(&:to_i)                    # => [10, 1000000000]
WV = N.times.collect { gets.split.collect(&:to_i) }  # => [[80000000, 99], [11000000, 119], [12000000, 150], [15000000, 174], [16000000, 168], [18000000, 190], [19000000, 187], [25000000, 273], [28000000, 307], [30000000, 319]]

# 最大公約数で桁を下げる
if true
  gcd = [W, *WV.collect(&:first)].reduce(:gcd)       # => 1000000
  W /= gcd                                           # => 1000
  WV.collect! { |w, v| [w / gcd, v] }                # => [[80, 99], [11, 119], [12, 150], [15, 174], [16, 168], [18, 190], [19, 187], [25, 273], [28, 307], [30, 319]]
end

WV.unshift(nil)                                      # => [nil, [80, 99], [11, 119], [12, 150], [15, 174], [16, 168], [18, 190], [19, 187], [25, 273], [28, 307], [30, 319]]
dp = Array.new(N.next) { Array.new(W.next, -Float::INFINITY) } # -無限大 で初期化する
dp[0][0] = 0
(1..N).each do |y|                  # 縦軸: 1..アイテム数
  (0..W).each do |x|                # 横軸: 0..容量
    w, v = WV[y]                    # w:大きさ v:価値
    if x < w
      # y 番目のアイテムが使えない
      dp[y][x] = dp[y - 1][x]
    else
      # y 番目のアイテムが使えるが、使わない or 使う
      dp[y][x] = [dp[y - 1][x], (dp[y - 1][x - w]) + v].max
    end
  end
end
p dp[N].max                                          # => 1986

ナップサックの容量とアイテムの大きさの最大公約数を求めて各値を小さくする。これによってアイテム1の大きさ 80000000 は 80 になる、としたのだが違うようだ。TLE ならまだしも RE になる理由もよくわからない。

解説の模範解答 (AC)

1263 ms

N, W = gets.split.collect(&:to_i)                    # => [10, 1000000000]
WV = N.times.collect { gets.split.collect(&:to_i) }  # => [[80000000, 99], [11000000, 119], [12000000, 150], [15000000, 174], [16000000, 168], [18000000, 190], [19000000, 187], [25000000, 273], [28000000, 307], [30000000, 319]]
V = 1000 * N                                         # => 10000
WV.unshift(nil)                                      # => [nil, [80000000, 99], [11000000, 119], [12000000, 150], [15000000, 174], [16000000, 168], [18000000, 190], [19000000, 187], [25000000, 273], [28000000, 307], [30000000, 319]]
dp = Array.new(N.next) { Array.new(V.next, Float::INFINITY) } # 無限大で初期化する
dp[0][0] = 0
(1..N).each do |y|                  # 縦軸: 1..アイテム数
  (0..V).each do |x|                # 横軸: 0..想定される最大価値
    w, v = WV[y]                    # w:大きさ v:価値
    if x < v
      # y 番目のアイテムが使えない
      dp[y][x] = dp[y - 1][x]
    else
      # y 番目のアイテムが使えるが、使わない or 使う
      dp[y][x] = [dp[y - 1][x], dp[y - 1][x - v] + w].min
    end
  end
end
value = 0
dp[N].each.with_index do |e, x|
  if e <= W
    value = x
  end
end
p value                                              # => 1986

大きさと価値を入れ替えて価値を横軸にする。

大きさと価値の関係と計算方法まとめ

	大きさ < 価値 (前回の問題)	価値 < 大きさ (今回の問題)
考え方	横幅を大きさにして価値を書く	横幅を価値にして大きさを書く
横軸	W (袋の大きさ)	V (想定される最大価値)
使う場合	dp[y - 1][x - w] + v	dp[y - 1][x - v] + w
比較	max ※価値を最大にしたいから	min ※大きさを最小にしたいから
答え	最後の行の最大値	最後の行の袋の大きさW以下の最大値の位置

計算量を減らす工夫として着目する点は、表の横幅をなるべく小さくしたいということ。つまり「大きさ」と「価値」で小さい方を横幅にする。

想定される最大価値 V が、どこから来るのかわかりづらいが、アイテム1つあたり最大 1000 と問題に示されているので 1000 * N としている。