【Ruby】動的計画法を考える③「部分和問題」

10になるカードの組み合わせはある？

数字の書かれたカードが並んでいる。
この中から好きなカードを選び、書かれた数字の合計が10になる組み合わせは存在するか？
このような「部分和問題」を「動的計画法」を使って効率よく解く方法を考える。

→②ナップサック問題

部分和問題を考える

部分和問題はナップサック問題の一種として考えることができる。
ナップサック問題では要素(荷物)に

• 重さ
• 価値

という二つの属性があったが、部分和問題では「重さ=価値」として扱える。

また、動的計画法にて計算をメモする場合、通常のナップサック問題では

memo[i][j] = v # i番目の要素を選択すると残りの持てる重さはj、その際の価値はv

というようにメモしていた。
しかし部分和問題では重さ=価値、j = v。
jはメモに記録されるのだから、vにはその組み合わせが「存在する印」をつけるだけでいい。
つまり、vの値は「存在するor存在しない」の二択、真偽値またはビットに省略できる。

実装

ループ

ITEM = [3, 4, 5, 6]

# 要素数
N = ITEM.size

# 目標
A = 10

memo = Array.new(N + 1) { Array.new(A + 1, false) }
memo[0][0] = true

i = 0
while i < N
  j = 0
  while j <= A
    v = ITEM[i]
    memo[i + 1][j] ||= memo[i][j] || (j >= v && memo[i][j - v])
    j += 1
  end
  i += 1
end

puts memo[N][A] # => true

「memo[0][0] = true」については、
「合計が0になる組み合わせは、要素を一つも選ばなければ常に達成できる」
という前提をもとに初期化している。

ビットDP

ITEM = [3, 4, 5, 6]

# 要素数
N = ITEM.size

# 目標
A = 10

r = 1
i = 0
while i < N
  r |= r << ITEM[i]
  i += 1
end

puts ((r >> A) & 1) == 1 # => true

部分和問題を解く上で必要な情報は、目標値になる組み合わせが存在するかどうか。
これはなんと、2進数で管理し、ビット演算だけで計算できてしまう。

r = 1に対し、まずは、3のカードがきた場合、rの値は以下の様に変化する。

0001 |= (0001 << 3)
↓
0001 |= 1000
↓
1001

0と3番目のビットが立っていることが分かる。
次に、4のカードが来た場合を考える。
現時点では3のカードに4のカードを加える場合と、カード無しに4を加える場合があるので…

00001001 |= (0001001 << 4)
↓
00001001 |= 10010000
↓
10011001

0, 3, 4, 7になる組み合わせのカードがあり、そのビットが立っていることが分かる。
このように、ビットシフトとOR演算だけで、組み合わせの加算を計算できる。
計算を終えたら、あとは目標値A番目のビットが立っているかを調べるだけ。
巨大な値や長大なビット列を扱えるプログラミング言語であれば簡潔に書けていい。

書こうと思えば1行でも、しかも割と分かりやすく書けてしまう。

puts ITEM.inject(1) { |r, i| r |= r << i }[A] == 1