我尝试用Python
实现背包问题的分支定界方法。
def bound(vw, v, w, idx):
if idx >= len(vw) or w > limit:
return -1
else:
while idx < len(vw) and w + vw[idx][1] <= limit:
v, w, idx = v+vw[idx][0], w+vw[idx][1], idx + 1
if idx < len(vw):
v += (limit - w)*vw[idx][0]/(vw[idx][1] * 1.0)
return v
def knapsack(vw, limit, curValue, curWeight, curIndex):
global maxValue
if bound(vw, curValue, curWeight, curIndex) >= maxValue:
if curWeight + vw[curIndex][1] <= limit:
maxValue = max(maxValue, curValue + vw[curIndex][0])
knapsack(vw, limit, curValue + vw[curIndex][0], curWeight + vw[curIndex][1], curIndex+1)
if curIndex < len(vw) - 1:
knapsack(vw, limit, curValue, curWeight, curIndex+1)
return maxValue
maxValue = 0
def test():
with open(sys.argv[1] if len(sys.argv) > 1 else sys.exit(1)) as f:
limit, n = map(int, f.readline().split())
vw = []
for ln in f.readlines():
vl, wl = map(int, ln.split())
vw.append([vl, wl, vl/(wl*1.0)])
knapsack(sorted(vw, key=lambda x: x[2], reverse=True), limit)
我有两个问题:
- 以上代码的时间复杂度是多少
- 对上述代码有任何改进或优化吗
一般来说,CS理论家发现分支定界算法极难分析:例如,请参阅此处进行一些讨论。您总是可以采用完整的枚举边界,这通常很容易计算,但通常也非常宽松。
我发现它可以用priority-queue
进行优化
def knapsack(vw, limit):
maxValue = 0
PQ = [[-bound(0, 0, 0), 0, 0, 0]]
while PQ:
b, v, w, j = heappop(PQ)
if b <= -maxValue:
if w + vw[j][1] <= limit:
maxValue = max(maxValue, v + vw[j][0])
heappush(PQ, [-bound(v+vw[j][0], w+vw[j][1], j+1),
v+vw[j][0], w+vw[j][1], j+1])
if j < len(vw) - 1:
heappush(PQ, [-bound(v, w, j+1), v, w, j+1])
return maxValue