01背包問題

遞歸方式模板：

void backtrack(int t){ if(t > n) output(x); else{ for(int i = f(n,t); i <= g(n,t);i++){ x[t] = h(i); if(constraint(t) && bound(t)) backtrack(t+1); } } }

遞歸實現：分成３個部分，為了使用限界函數，需要把數據降序排序，限界函數，以及回溯函數。

def pack_01_back_prune(N,V,C,W):BestResult = [False]*NSelected = [False]*(N)BestValue = [0]CurCost = [0]CurValue = [0]order = [i for i in range(N)]perp = [0]*N# sorted by value per weightdef sort_group(C,W,O):perp = [0]*Nfor i in range(N):perp[i] = W[i]/C[i]for i in range(N-1):for j in range(i+1,N):if perp[i] < perp[j]:temp = perp[i]perp[i] = perp[j]perp[j] = temptemp = O[i]O[i] = O[j]O[j] = temptemp = C[i]C[i] = C[j]C[j] = temptemp = W[i]W[i] = W[j]W[j] = temp return perp,C,W,O # 計算上界函數，功能為剪枝 # 判斷當前背包的總價值cp＋剩余容量可容納的最大價值<=當前最優價值def bound(depth):left_weight = V - CurCost[0]b = CurValue[0] while depth < N and C[depth] <= left_weight:left_weight -=C[depth]b += W[depth]depth +=1if depth < N:b += perp[depth] * left_weightreturn bdef backtracking(depth):if depth > N-1:if CurValue[0] > BestValue[0]:BestValue[0] = CurValue[0] BestResult[:] = Selected[:]else: # 如若左子節點可行，則直接搜索左子樹; # 對于右子樹，先計算上界函數，以判斷是否將其減去if CurCost[0] + C[depth] <= V :# and bound(depth+1) > BestValue[0]:Selected[depth] = TrueCurCost[0] += C[depth]CurValue[0] += W[depth]# nextbacktracking(depth+1)# undoCurCost[0] -= C[depth]CurValue[0] -= W[depth] # 如若符合條件則搜索右子樹 if bound(depth+1) > BestValue[0]:Selected[depth] = Falsebacktracking(depth+1)perp,C,W,order = sort_group(C,W,order)backtracking(0)# 把結果恢復成原來順序decode_BestResult =[False]*Nfor i in range(N):if BestResult[i]:decode_BestResult[order[i]] = Truereturn decode_BestResult,BestValue

迭代方式，順序執行，注意一點，就是不滿足限界函數時，需要提前進入回溯

#%%def pack_01_back_prune_iteration(N,V,C,W):BestResult = [False]*NSelected = [False]*(N)BestValue = [0]CurCost = [0]CurValue = [0]order = [i for i in range(N)]perp = [0]*N# sorted by value per weightdef sort_group(C,W,O):perp = [0]*Nfor i in range(N):perp[i] = W[i]/C[i]for i in range(N-1):for j in range(i+1,N):if perp[i] < perp[j]:temp = perp[i]perp[i] = perp[j]perp[j] = temptemp = O[i]O[i] = O[j]O[j] = temptemp = C[i]C[i] = C[j]C[j] = temptemp = W[i]W[i] = W[j]W[j] = temp return perp,C,W,O # 計算上界函數，功能為剪枝 # 判斷當前背包的總價值cp＋剩余容量可容納的最大價值<=當前最優價值def bound(depth):left_weight = V - CurCost[0]b = CurValue[0] while depth < N and C[depth] <= left_weight:left_weight -=C[depth]b += W[depth]depth +=1if depth < N:b += perp[depth] * left_weightreturn bdef backtracking_iteration(depth):while True:if depth < N:# 進入１的分支if CurCost[0] + C[depth] <= V and bound(depth+1) > BestValue[0]:Selected[depth] = TrueCurCost[0] += C[depth]CurValue[0] += W[depth]# 進入０的分支elif bound(depth+1) > BestValue[0]:Selected[depth] = False# 不滿足限界函數，回溯 else:while depth >= 0 and not Selected[depth]:depth -=1if depth < 0:breakelse:Selected[depth] =FalseCurCost[0] -= C[depth]CurValue[0] -= W[depth] else:if CurValue[0] > BestValue[0]:BestValue[0] = CurValue[0] BestResult[:] = Selected[:]# 到底部回溯，這時候，depth已經穿了depth -=1while depth >= 0 and not Selected[depth]:depth -=1if depth < 0:breakelse:Selected[depth] =FalseCurCost[0] -= C[depth]CurValue[0] -= W[depth] depth +=1perp,C,W,order = sort_group(C,W,order)backtracking_iteration(0)decode_BestResult =[False]*Nfor i in range(N):if BestResult[i]:decode_BestResult[order[i]] = Truereturn decode_BestResult,BestValue

輸出結果

#%% N = 8 V = 30 C = [11,2,3,9,13,6,15,7,19] W = [5.0,2.0,5.0,7.0,5.0,11.0,6.0,14.0]#print pack_01_back(N,V,C,W) #print pack_01_back_iteration(N,V,C,W) #print pack_01_back_iteration2(N,V,C,W) print pack_01_back_prune(N,V,C,W) print pack_01_back_prune_iteration(N,V,C,W)runfile('/root/test/back_tracking.py', wdir='/root/test') ([False, True, True, True, False, True, False, True], [39.0])runfile('/root/test/back_tracking.py', wdir='/root/test') ([False, True, True, True, False, True, False, True], [39.0])

還有一種分支限界的思路，上界函數為：CurValue + rest <= BestValue：

# 這種解法注意回溯函數一致性，思路比較清晰：滿足剪枝條件就回溯：CurValue + rest <= BestValue def pack_01_back_iteration3(N,V,C,W):depth = 0BestResult = [False]*NSelected = [False]*(N)BestValue = 0CurCost = 0CurValue = 0 rest = 0for i in range(N):rest += W[i]while True:while depth < N and CurCost + C[depth] <= V:rest -=W[depth]Selected[depth] = TrueCurCost += C[depth]CurValue += W[depth]depth +=1if depth >= N:BestValue = CurValue BestResult[:] = Selected[:]else:rest -=W[depth]Selected[depth] =Falsedepth +=1while CurValue + rest <= BestValue:depth -=1while depth >=0 and not Selected[depth]:rest +=W[depth]depth -=1if depth < 0:return BestResult,BestValueelse:Selected[depth] =FalseCurCost -= C[depth]CurValue -= W[depth]depth +=1N = 8 V = 30 C = [11,2,3,9,13,6,15,7,19] W = [5.0,2.0,5.0,7.0,5.0,11.0,6.0,14.0]print pack_01_back_iteration3(N,V,C,W)([False, True, True, True, False, True, False, True], 39.0)

總結

以上是生活随笔為你收集整理的01背包问题：回溯法和限界分支、递归和迭代方式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。