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

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

問題定義

品物が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]