ナップサック問題について整理

どういうときに何ができるのかについて。この辺見ながら。

問題定義

品物がN個あったとする。品物iには価値c_iと体積a_iが与えられている。x_iは1のとき品物iを取る、0のときに取らないということを表すバイナリ変数であるとする。持って行ける品物の総体積がbまでであるとすると、ナップサック問題は以下の最適化問題として定式化される。

  • 最大化: \sum_{i=1}^N c_i x_i
  • 制約: \sum_{i=1}^N a_i x_i \leq b かつ x_i \in \{0, 1\}, i = 1, ..., N

これを真面目に列挙して解こうとするとO(2^N)となって多項式時間では解けない。x_i \in \{0, 1\}の部分を0 \leq x_i \leq 1という風に連続緩和してやれば解は閉じた形で書き表すことができる(c_i / a_iでソートしてやって、でかい順に詰めていく。最後のやつは入る分だけ詰める)。

動的計画法

ここで、体積a_iとbを「整数」であると仮定する。V_k(y)を体積yの中に詰める品物の候補をG_1, ..., G_kに限定したときに得られる最大の価値と定義する。すると元の問題の最適解はV_n(b)がfeasibleのときに達成される。こういう定義をすると、動的計画法かと検討が付くがV_k(y)は以下のように書ける。
V_k(y) = \mbox{max}\{V_{k - 1}(y), V_{k - 1}(y - a_k) + c_k\}
10秒くらいじっと見ると分かる。後はいつものごとくDP tableを作っていって、バックトラックして最適解を求めることができる。

bが「整数」でないとDPを使えないのはDP tableがそもそも作れなくなるからすぐ分かる。体積a_iのほうも整数でないといけないのはDPの式の中でV_{k - 1}(y - a_k)という項があるからで、a_kが実数だとDP tableが破綻するから。

まとめ

  • そのままだと多項式時間じゃ無理
  • 連続緩和すれば閉じた形でできる
  • 制約に関する項が整数であれば動的計画法を使って多項式時間で解ける

おまけ

DPの例をpythonでやってみた、というだけ。

values = [7, 9, 5, 5]
costs = [3, 6, 4, 5]
constrain = 12

dp_table = [[0 for j in range(constrain)] for i in range(len(values))]
backtrack = [[0 for j in range(constrain)] for i in range(len(values))]

# initialization
for y in range(constrain):
    if costs[0] <= y + 1:
        dp_table[0][y] = values[0]
        backtrack[0][y] = 1
    else:
        backtrack[0][y] = 0

# DP construction
for k in xrange(1, len(values)):
    for y in range(constrain):
        if y - costs[k] < 0: # out of range
            dp_table[k][y] = dp_table[k - 1][y]
            backtrack[k][y] = 0
            continue
        left = dp_table[k - 1][y]
        right = dp_table[k - 1][y - costs[k]] + values[k]
        if left < right: # update
            dp_table[k][y] = right
            backtrack[k][y] = 1
        else:
            dp_table[k][y] = left
            backtrack[k][y] = 0

argmax = []
prev = backtrack[len(values) - 1][constrain - 1]
argmax.append(prev)

tmp_constrain = constrain - 1

for k in xrange(len(values) - 2, -1, - 1):
    if prev is 1: # case previous item was selected
        tmp_constrain -= costs[k + 1]
        prev = backtrack[k][tmp_constrain]
    else:
        prev = backtrack[k][tmp_constrain]
    argmax.append(prev)
argmax.reverse()
            
print dp_table
print backtrack
print argmax

実行結果。

% python knapsack.py
[[0, 0, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7], [0, 0, 7, 7, 7, 7, 9, 9, 16, 16, 16, 16], [0, 0, 7, 7, 7, 7, 12, 12, 16, 16, 16, 16], [0, 0, 7, 7, 7, 7, 12, 12, 16, 16, 16, 17]]
[[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]
[1, 0, 1, 1]

アルゴリズムデザイン

アルゴリズムデザイン

  • 作者: Jon Kleinberg,Eva Tardos,浅野孝夫,浅野泰仁,小野孝男,平田富夫
  • 出版社/メーカー: 共立出版
  • 発売日: 2008/07/10
  • メディア: 単行本
  • 購入: 10人 クリック: 421回
  • この商品を含むブログ (51件) を見る