限界分支法：隊列實現(xiàn)方式

前面已經(jīng)介紹過限界分支法大部分是基于廣度優(yōu)先搜索，廣度優(yōu)先搜索一般借助于隊列實現(xiàn)，剪枝的情況可以借助于優(yōu)先級隊列。

實現(xiàn)如下：

#%% class FIFO_01_Pack:def __init__(self,N,V,C,W):self.num =Nself.Volume = Vself.Cost = Cself.Value = Wself.BestValue = 0#用于存放活結(jié)點，便于理解，把根結(jié)點，以及第0層結(jié)束標志-1放進去# 結(jié)點包括2個屬性：當前空間大小，當前的價值大小self.queue = [[0,0],[-1,-1],] # 實現(xiàn)時葉子結(jié)點不加入到活結(jié)點列表，當屬于葉子結(jié)點時，增加對結(jié)果的處理def enQueen(self,pair,depth):if depth == self.num -1:CurValue = pair[1]if CurValue > self.BestValue:self.BestValue = CurValueelse:self.queue.append(pair)def pack_01(self): # selected = [0]*self.num # 首先取出根結(jié)點depth = 0pair = self.queue.pop(0)CurCost = pair[0]CurValue = pair[1]while True:# 判斷左結(jié)點能否加入到隊列，能的話，把當前空間和當前價值放入隊列if CurCost + self.Cost[depth] < self.Volume:self.enQueen([CurCost + self.Cost[depth],CurValue + self.Value[depth]],depth)# 右結(jié)點總是可以加入隊列的，因為沒有約束條件的限制self.enQueen([CurCost,CurValue],depth)# 然后彈出下一個結(jié)點pair = self.queue.pop(0)CurCost = pair[0]CurValue = pair[1]# 當同一層處理完畢時，先判斷是否能夠輸出結(jié)果，判斷的標準是隊列是否為空，# 這時下一層的所有結(jié)點已經(jīng)加入了隊列，這時需要把下一層# 增加一個結(jié)尾-1便于判斷，然后進入下一層，彈出下一個結(jié)點if CurCost == -1:if not self.queue:return self.BestValueself.enQueen([-1,-1],depth)depth += 1pair = self.queue.pop(0)CurCost = pair[0]CurValue = pair[1]def print_Result(self):print(self.pack_01())

Baseline對比及結(jié)果輸出：

class pack_01_back_test: def __init__(self,N,V,C,W):self.num =Nself.V = Vself.C = Cself.W = Wself.BestResult = [False]*Nself.Selected = [False]*Nself.BestValue = 0self.CurCost = 0self.CurValue = 0def pack_01_back_tracking(self,depth):if depth > self.num-1:if self.CurValue > self.BestValue:self.BestValue = self.CurValue self.BestResult[:] = self.Selected[:]else:if self.CurCost + self.C[depth] <= self.V:self.Selected[depth] = Trueself.CurCost += self.C[depth]self.CurValue += self.W[depth]# nextself.pack_01_back_tracking(depth+1)# undoself.CurCost -= self.C[depth]self.CurValue -= self.W[depth]self.Selected[depth] = Falseself.pack_01_back_tracking(depth+1)def print_Result(self):self.pack_01_back_tracking(0)print(self.BestResult)print(self.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]pack_01_back_test(N,V,C,W).print_Result() FIFO_01_Pack(N,V,C,W).print_Result()[False, True, True, True, False, True, False, True] 39.0 39.0

追蹤解

追蹤解，上述實現(xiàn)的情況下，解都在最后一層，根本不知道之前的路徑是怎樣的，廣度優(yōu)先搜索，同一個緯度，假如不加指標判斷的話，根本不知道最優(yōu)解是選擇的哪一個，所以需要同一個緯度的每一個結(jié)點，記住他之前的路徑，才能在最優(yōu)解的時候之前是怎么走過來的，每一個結(jié)點用一個數(shù)組記錄路徑，這樣實現(xiàn)的感覺消耗有點大啊，通?？匆娛遣捎面湵矸绞?/p> 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結(jié)

以上是生活随笔為你收集整理的限界分支法（实际上没有剪枝，介绍的是广度优先搜索）：01背包问题，队列实现方式（FIFO）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。