どういうときに何ができるのかについて。この辺見ながら。
問題定義
品物がN個あったとする。品物iには価値- 最大化:
- 制約:
かつ
これを真面目に列挙して解こうとするとO(2^N)となって多項式時間では解けない。の部分を
という風に連続緩和してやれば解は閉じた形で書き表すことができる(
でソートしてやって、でかい順に詰めていく。最後のやつは入る分だけ詰める)。
動的計画法
ここで、体積10秒くらいじっと見ると分かる。後はいつものごとくDP tableを作っていって、バックトラックして最適解を求めることができる。
bが「整数」でないとDPを使えないのはDP tableがそもそも作れなくなるからすぐ分かる。体積のほうも整数でないといけないのはDPの式の中で
という項があるからで、
が実数だと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件) を見る