前面提到：

不知道大家注意到?jīng)]有？上述實(shí)現(xiàn)方式?jīng)]有使用單位體積價(jià)值的排序，和之前提到01背包回溯法基于單位體積價(jià)值實(shí)現(xiàn)不一樣（先裝單位體積價(jià)值高的）。

我們網(wǎng)上經(jīng)常看到都是基于以上實(shí)現(xiàn)的，到底這個(gè)用有什么好處了？實(shí)際上基于排序的單位體積價(jià)值是一個(gè)非常精確的限界函數(shù)

基于優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)方式，就需要用到以上的結(jié)構(gòu)：

優(yōu)先級(jí)隊(duì)列方式需要數(shù)據(jù)預(yù)處理，為什么需要預(yù)處理數(shù)據(jù)了，這里使用的是優(yōu)先級(jí)隊(duì)列，這個(gè)優(yōu)先級(jí)的選區(qū)非常重要，也非常重要
之前的策略curValue+rest就不行了，不是不行，是不夠好，那是一個(gè)粗糙的界，可以看到一開(kāi)始選的就不是最優(yōu)，然后又往回跳躍，因?yàn)樵谶@種策略下，無(wú)法保證最優(yōu)，這時(shí)需要精心挑選優(yōu)先級(jí)，使之盡可能少往回跳躍或者跳低點(diǎn)，就像思考貪心策略那樣，實(shí)際上就是思考貪心策略，貪心就是配合優(yōu)先級(jí)隊(duì)列使用的這里首先把數(shù)據(jù)安裝單位體積價(jià)值降序排列。

代碼實(shí)現(xiàn)如下：

import heapq class Nodes:def __init__(self,CurValue=None,CurCost=None,depth =None,parent=None,Flag=None):# 部分解所占體積self.CurCost = CurCost# 部分解所占價(jià)值self.CurValue = CurValue# 處于那一層self.depth = depth# 當(dāng)前結(jié)點(diǎn)是否選擇了物品 self.isleft = Flag# 前一個(gè)結(jié)點(diǎn)是誰(shuí)self.parent = parentclass PQ_pack_01_with_solution_tracking:def __init__(self,N,V,C,W):self.num = Nself.volume = Vself.cost = Cself.value = W#(0當(dāng)前的價(jià)值，1,當(dāng)前體積，2當(dāng)前的深度，3父節(jié)點(diǎn)，4是否選擇了該物品)self.bestnode = Nodes(0,0,0,None,False)# 保存最后的方案self.bestsolution = [False]*N# 數(shù)據(jù)預(yù)處理，為什么需要預(yù)處理數(shù)據(jù)了，這里使用的是優(yōu)先級(jí)隊(duì)列，這個(gè)優(yōu)先級(jí)的選區(qū)非常重要，也非常重要# 之前的策略curValue+rest就不行了，因?yàn)樵谶@種策略下，無(wú)法保證最優(yōu)，這時(shí)需要精心挑選優(yōu)先級(jí)，就像# 思考貪心策略那樣，實(shí)際上就是思考貪心策略，貪心就是配合優(yōu)先級(jí)隊(duì)列使用的# 這里首先把數(shù)據(jù)安裝單位體積價(jià)值降序排列，self.order記錄與之前排列的標(biāo)號(hào)，用于恢復(fù)最后結(jié)果self._cost,self._value,self.order = self.sort_group(N,C,W)# 把數(shù)據(jù)安裝單位體積價(jià)值降序排列def sort_group(self,N,C,W):# 原來(lái)數(shù)據(jù)的標(biāo)號(hào)O = [i for i in range(N)]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 C,W,O# 限界函數(shù)，這個(gè)限界函數(shù)就非常精確，確保了每一次往下都是最優(yōu)的策略def bound(self,depth,CurCost,CurValue):left_weight = self.volume - CurCostb = CurValuewhile depth < self.num and self._cost[depth] <= left_weight:left_weight -=self._cost[depth]b += self._value[depth]depth +=1if depth < N:b += (self._value[depth]/self._cost[depth]) * left_weightreturn bdef PQ_pack_01(self):pqueue = [] # 初始化，從root開(kāi)始current_node = Nonecurrent_value = 0current_cost = 0depth = 0# 終止條件，優(yōu)先級(jí)隊(duì)列里面存的是(0當(dāng)前的價(jià)值，1,當(dāng)前體積，2當(dāng)前的深度，3父節(jié)點(diǎn)，4是否選擇了該物品)# 只要取第self.num層最優(yōu)的current_value就可以了，只要到self.num層終止就行了while depth != self.num:# 滿足約束條件，存入左結(jié)點(diǎn)if current_cost + self._cost[depth] <= self.volume:# 每次進(jìn)入左結(jié)點(diǎn)更新最優(yōu)質(zhì)，這樣方便剪枝，讓沒(méi)有必要的點(diǎn)不放進(jìn)優(yōu)先級(jí)隊(duì)列if current_value + self._value[depth] > self.bestnode.CurValue:self.bestnode.CurValue =current_value + self._value[depth]# 確定待放入結(jié)點(diǎn)的上界temp = self.bound(depth+1,current_cost+self._cost[depth],current_value+self._value[depth])# 把待放入結(jié)點(diǎn)的上界，當(dāng)前價(jià)值，當(dāng)前花費(fèi)，當(dāng)前層次，父親，是左是右放入優(yōu)先級(jí)隊(duì)列# 因?yàn)槭且笞畲蠖?#xff0c;隨意優(yōu)先級(jí)取了-，heapq默認(rèn)是取最小堆，直接求最大堆的包還不知道怎么用heapq.heappush(pqueue,(-temp,Nodes(current_value + self.value[depth],current_cost+self._cost[depth],depth+1,current_node,True)))# 對(duì)于右結(jié)點(diǎn)計(jì)算上界up = self.bound(depth+1,current_cost,current_value)# 加入上界小于當(dāng)前最優(yōu)質(zhì)，就沒(méi)有必要放入優(yōu)先級(jí)隊(duì)列，免得給優(yōu)先級(jí)隊(duì)列增加負(fù)擔(dān)# 等于的情況需要放進(jìn)去，因?yàn)檫@時(shí)路徑必須的，沒(méi)有等于0，就沒(méi)法深入了if up >= self.bestnode.CurValue:heapq.heappush(pqueue,(-up,Nodes(current_value,current_cost,depth+1,current_node,False)))# 彈出下一個(gè)最優(yōu)的結(jié)點(diǎn)，0代表上界，1包含了所需要的信息current_node = heapq.heappop(pqueue)[1]current_value = current_node.CurValuecurrent_cost = current_node.CurCostdepth = current_node.depthprint(depth,current_value)self.bestnode = current_nodeprint(self.bestnode.CurValue)# 追蹤解 def solution_tracking(self):# 追蹤解，獲取最優(yōu)方案BestResult =[False]*Nfor i in range(self.num -1,-1,-1):BestResult[i] = self.bestnode.isleftself.bestnode = self.bestnode.parent# 將最優(yōu)方案翻譯成原來(lái)的排序 for i in range(N):if BestResult[i]:self.bestsolution[self.order[i]] = Trueprint(self.bestsolution)N = 8 V = 30 C = [11,2,3,9,13,6,15,7] W = [5.0,2.0,5.0,7.0,5.0,11.0,6.0,14.0]tt =PQ_pack_01_with_solution_tracking(N,V,C,W) tt.PQ_pack_01() tt.solution_tracking()1 14.0 2 25.0 3 30.0 4 32.0 5 39.0 6 39.0 7 39.0 4 30.0 8 39.0 39.0 [False, True, True, True, False, True, False, True]

總結(jié)

以上是生活随笔為你收集整理的限界分支法：01背包问题，优先级队列（包含解的追踪）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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