🐸

[鉄則B18] Subset Sum with Restoration

2024/03/26に公開

Ruby

二次元の動的計画法の応用で経路を復元する問題。

問題の要約

N 枚のカードから何枚かを選択して合計が S になるか？
なるのであれば、それは何のカードたちを選択したときか？

例1で問題を理解する

2 2 3 の値が書かれた 3 枚のカードから 2 2 3 を選択したとき合計 7 になる
したがってカード番号 1 2 3 が答えになる

現実的には 2 2 3 の方を知りたい気がするがこの手の問題はカード番号を答えることが多い。

2つの方法の特徴

dp を逆に辿る方法
- 可能かどうかを求める処理部分はそのままでよい
- 復元が複雑になる
足跡を逆に辿る方法
- 可能かどうかを求める処理に足跡を記録する処理を入れる
- 復元がシンプルになる

どちらにも一長一短ある。

参考:

dp を逆に辿る方法 (AC)

N, S = gets.split.collect(&:to_i)  # => [10, 100]
A = gets.split.collect(&:to_i)     # => [14, 23, 18, 7, 11, 23, 23, 5, 8, 2]
A.unshift(nil)                     # => [nil, 14, 23, 18, 7, 11, 23, 23, 5, 8, 2]
dp = Array.new(N.next) { Array.new(S.next) }
dp[0][0] = true
(1..N).each do |y|
  (0..S).each do |x|
    dp[y][x] = dp[y - 1][x] || (x >= A[y]) && dp[y - 1][x - A[y]]
  end
end
dp[N][S]                           # => true

# ------------ ここまでは基礎問題と同じ ------------

# 復元 (面倒)
x = S
routes = []
N.downto(1) do |y|
  if dp[y][x]
    if x >= A[y]
      if dp[y - 1][x - A[y]] == dp[y][x] # 左上から来ているか？
        x = x - A[y]               # => 98, 90, 85, 62, 39, 32, 14, 0
        routes.unshift(y)
      end
    end
  end
end

routes.size                        # => 8
routes                             # => [1, 3, 4, 6, 7, 8, 9, 10]
routes.sum { |e| A[e] }            # => 100

if routes.empty?
  p -1
else
  p routes.size
  puts routes * " "
end

右下から左上に遡っていく
Y 軸は常にデクリメントする
X 軸はカードを選択したときだけ左に移動する
x < A[y] の場合 y 番目のカードを選択できていないケースなので見なくてよい

足跡を逆に辿る方法 (AC)

N, S = gets.split.collect(&:to_i)  # => [10, 100]
A = gets.split.collect(&:to_i)     # => [14, 23, 18, 7, 11, 23, 23, 5, 8, 2]
A.unshift(nil)                     # => [nil, 14, 23, 18, 7, 11, 23, 23, 5, 8, 2]
if true
  predecessor = Array.new(N.next) { Array.new(S.next) } # 足跡用
end
dp = Array.new(N.next) { Array.new(S.next) }
dp[0][0] = true
(1..N).each do |y|              # (1..カード枚数)
  (0..S).each do |x|            # (0..合計値)
    dp[y][x] = dp[y - 1][x] || (x >= A[y]) && dp[y - 1][x - A[y]]
    # カードを選択したのは左上から来た場合なのでその場合のみ足跡を記録する
    if true
      if x >= A[y] && dp[y][x] == dp[y - 1][x - A[y]]
        if dp[y][x]
          predecessor[y][x] = [y - 1, x - A[y]] # 足跡を記録
        end
      end
    end
  end
end
dp[N][S]                           # => true

# 復元 (足跡を見るだけなので簡単)
routes = []
x = S                              # => 100
N.downto(1) do |y|
  if predecessor[y][x]
    routes.unshift(y)
    _, x = predecessor[y][x]
  end
end

routes.size                        # => 8
routes                             # => [1, 3, 4, 6, 7, 8, 9, 10]
routes.sum { |e| A[e] }            # => 100

if routes.empty?
  p -1
else
  p routes.size
  puts routes * " "
end

使う場合のみ足跡を残す
足跡用の変数を別に用意するのではなく dp に足跡を一緒に入れる方法もあり
dp[N][S] が偽の時点で -1 としてもよい

問題の要約

例1で問題を理解する

2つの方法の特徴

dp を逆に辿る方法 (AC)

足跡を逆に辿る方法 (AC)

Discussion