什麼是分支和束縛揹包的時間複雜性

Question

我試圖用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) 

在這裏，我有兩個問題：

• 什麼是上面的代碼的時間複雜度？
• 上述代碼的任何改進或優化？

Answer 1

作爲一般規則，CS理論學家發現分支定界算法極難分析：例如， here進行一些討論。您始終可以採用全枚舉界限，這通常很容易計算 - 但它通常也非常鬆散。

Answer 2

我發現它可能與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 

進行優化