地上の洞窟

どこにも行かず、液晶と「にらめっこ」し続ける人の物語。

【Ruby】動的計画法を考える②「ナップサック問題」

Ruby
ナップサック問題
どれを持ち帰る？

冒険者が旅の途中、たくさんの宝物を見つけました。
しかし、持ち帰れるのは8kgまでです。
持ち帰る宝物の価値が最も高くなるには、どれを持ち帰ればいいのか。
それを知るべく我々はアマゾンの奥地「動的計画法」の奥地へ向かった・・・。

→その①「フィボナッチ数列」
→その③「部分和問題」

ナップサック問題を考える

冒頭に挙げたような問題は「ナップサック問題」と呼ばれる。
組合せ最適化問題の一つだ。

問題を解くには、各要素を選ぶor選ばないの二択で考えていく。
二択が要素数の分だけ掛け合わされて増えるため、パターンの数は 2^nとなる。
(要素の数 n=5 なら 2\times2\times2\times2\times2=2^5=32 通り)

これを愚直に調べるとなると、n=20で約100万通り、n=40で約1兆通り。
二桁程度の要素数増加で、いともたやすく処理不能になる。

bit全探索

それでも n=20 程度であれば、現実的な時間で調べ上げることができる。
この場合「bit全探索」という方法が使える。
選ぶか選ばないかの二択ということは、各要素は2ビット。
それが要素数の分だけ並んでいて、取り得る値は 2^n通り。
つまり 0 ～ 2^n-1 までの値でループさせビットを取れば、簡単に全通りを調べ上げられる。

実装
# 宝物 [重さ, 価値]
ITEM = [
  [3, 25],
  [1, 10],
  [6, 70],
  [2, 15]
]

# 持ち帰れる重さの上限
W = 8

# 要素数
N = ITEM.size

i = 0
s = 1 << N # 2 ** N
max = 0

while i < s
  cw = 0
  cv = 0
  j = 0
  while j < N
    # j番目のアイテムが選ばれているか？
    if (i & 1 << j) > 0
      w, v = ITEM[j]
      cw += w
      break if cw > W
      cv += v
    end
    j += 1
  end
  max = cv if max < cv
  i += 1
end

puts max # => 85

動的計画法

ナップサック問題では、要素を「選択or未選択」の両方の価値を計算し、メモしていく。
その際、

  • [i]番目の要素を選ぶ時点で
  • 重さの合計は[j]

という二つの属性が付くため、メモ自体も二次元配列で作成する。
同じ重さで価値の高い選択があれば、価値の高い方をメモする。

実装

メモ化再帰
ITEM = [
  [3, 25],
  [1, 10],
  [6, 70],
  [2, 15]
]

W = 8
N = ITEM.size

@memo = Array.new(N + 1) { [] }

def f(i, j)
  return @memo[i][j] ||= (
    if i == N
      0 # 無効な値
    else
      w, v = ITEM[i]
      if j < w
        # 要素を選択しない(重量オーバー)
        f(i + 1, j)
      else
        # 要素を選択する or 要素を選択しない
        # 価値の高い方をメモ
        (r0 = f(k = i + 1, j)) > (r1 = f(k, j - w) + v) ? r0 : r1
      end
    end
  )
end

puts f(0, W) # => 85

要素数が4ケタ超えたあたりで再帰の上限に刺さってしまった。

ループ
ITEM = [
  [3, 25],
  [1, 10],
  [6, 70],
  [2, 15]
]

W = 8
N = ITEM.size

memo = Array.new(N + 1) { Array.new(W + 1, 0) }

i = 0
while i < N
  j = 0
  while j <= W
    w, v = ITEM[i]
    if w <= j
      memo[i + 1][j] = (x = memo[i][j]) > (y = memo[i][j - w] + v) ? x : y
    else
      memo[i + 1][j] = memo[i][j]
    end
    j += 1
  end
  i += 1
end

puts memo[N][W] # => 85

計算量は O(NW) 。
再帰に比べ W が大きいと処理が非効率になるデメリットがある。
一括処理のため要素の選択で変化する重さを捉えられない。
メモ登録時にキューに登録するなどしようとしても、今度は変化する重さのパターン自体が膨大ゆえに、キューの制作コストでかえって非効率。

ループ(一次元配列メモ)
ITEM = [
  [3, 25],
  [1, 10],
  [6, 70],
  [2, 15]
]

W = 8
N = ITEM.size

memo = Array.new(W + 1, 0)

i = 0
while i < N
  j = W
  while j >= 0
    w, v = ITEM[i]
    if w <= j
      memo[j] = (x = memo[j]) > (y = memo[j - w] + v) ? x : y
    end
    j -= 1
  end
  i += 1
end

puts memo[W] # => 85

上二つで実際にやっていることは、重さごとの価値の最大値の更新である。
故に一次元配列でも実装可能。
重さに関するループは逆順に回すこと。
でないと１ループ内で更新後の値を拾ってしまい、計算結果がおかしくなる。

選択した要素の取得

ここまで計算してきたのは、要素を最善で選んだ場合の「価値」の値そのものである。
しかし実際に知りたいのは「どの要素を選択したのか」というところではなかろうか。

選択状況を記録

要素を選択したかどうかを記録し辿れば、選んだ要素の取得ができる。
アルゴリズム的とは言えないごり押しだが。

srand(334)
ITEM = Array.new(30) do
  [rand(10) + 1, (rand(10) + 1) * 5]
end

W = 100
N = ITEM.size

@memo = Array.new(N + 1) { [] }
@selected = Array.new(N + 1) { [] }

def f(i, j)
  return @memo[i][j] ||= (
    if i == N
      0 # 無効な値
    else
      w, v = ITEM[i]
      if j < w
        # 要素を選択しない(重量オーバー)
        f(i + 1, j)
      else
        # 要素を選択する or 要素を選択しない
        # 価値の高い方をメモ
        if (r0 = f(k = i + 1, j)) > (r1 = f(k, j - w) + v)
          r0
        else
          @selected[i][j] = true
          r1
        end
        
      end
    end
  )
end

puts f(0, W)

items = []
i = 0
j = W

while i < N
  if @selected[i][j]
    items << i
    j -= ITEM[i][0]
  end
  i += 1
end

items.each { |i| p ITEM[i] }

puts "weight : #{items.map { |i| ITEM[i][0] }.inject(:+)}"
puts "value  : #{items.map { |i| ITEM[i][1] }.inject(:+)}"

↓出力

745
[3, 15]
[3, 45]
[4, 50]
[7, 40]
[2, 50]
[9, 50]
[8, 45]
[3, 10]
[6, 30]
[4, 50]
[8, 45]
[6, 35]
[2, 35]
[3, 20]
[5, 45]
[10, 50]
[7, 45]
[1, 35]
[8, 40]
[1, 10]
weight : 100
value  : 745
メモから逆算

メモを逆算してもどの要素を組み合わせたかが分かるっぽい。

ITEM = [
  [3, 25],
  [1, 10],
  [6, 70],
  [2, 15]
]

W = 8
N = ITEM.size

memo = Array.new(N + 1) { Array.new(W + 1, 0) }

i = 0
while i < N
  j = 0
  while j <= W
    w, v = ITEM[i]
    if w <= j
      memo[i + 1][j] = (x = memo[i][j]) > (y = memo[i][j - w] + v) ? x : y
    else
      memo[i + 1][j] = memo[i][j]
    end
    j += 1
  end
  i += 1
end

puts memo[N][W] # => 85

# 逆算

i = N
w = W
v = memo[N][W]
list = []

while i > 0
  i -= 1
  iw, iv = ITEM[i]
  if memo[i][w - iw] == v - iv
    list << i
    w -= iw
    v -= iv
  end
end

p list.inject(0) { |o, i| o + ITEM[i][0] }
p list.inject(0) { |o, i| o + ITEM[i][1] }