本范例主要是通過(guò)分支界限法解決著名的0/1背包客問(wèn)題
問(wèn)題描述：
有件商品,記為
把敞。每件商品的重量和價(jià)值分別為
和
;
其中,
現(xiàn)在有一個(gè)背包幻妓，可以容納的最大重量為疆偿。
問(wèn)該背包可以包含的最大價(jià)值是多少易遣？
基本思路：
本問(wèn)題是一個(gè)典型的排列組合問(wèn)題彼妻，只要能滿足總重量小于背包的容量的所有組合中，找到那個(gè)價(jià)值最大的組合；
每一件商品都有2種選擇侨歉，要么包含該商品屋摇，要么不包含該商品
因此總共有種組合方式。當(dāng)N很大時(shí)幽邓，如果嘗試每一種組合方式炮温，將會(huì)使得計(jì)算量變得非常大。如下圖所示
上圖中每一個(gè)小圓圈都代表一個(gè)節(jié)點(diǎn)牵舵，對(duì)于每一個(gè)小節(jié)點(diǎn)柒啤，都擁有兩個(gè)分支，兩種選擇畸颅，即包不包含某一個(gè)商品担巩，這既是分支界限法種分支的由來(lái)。而界限是指我們做每一個(gè)選擇時(shí)没炒，我們先提前預(yù)估一下加入做了該選擇涛癌，可能出現(xiàn)的最優(yōu)或最差情況，即所謂的上界和下界
比如我們從零開(kāi)始送火，我們算一下最大價(jià)值是多少拳话？按照貪婪算法思想，我們商品已由單位重量?jī)r(jià)值進(jìn)行了從大到小的排列
那么開(kāi)始最大可能價(jià)值就是A,B,C全部包含种吸，D商品部分包含, 由于可以包含部分商品弃衍，因此本價(jià)值提供了可能最大價(jià)值的上限。
假如包含商品A坚俗，則上限還是250镜盯，假如不包含商品A，則上限計(jì)算應(yīng)是B坦冠，C的全部?jī)r(jià)值加D部分價(jià)值形耗，應(yīng)該是
分支界限法的思想就是不斷選擇那個(gè)預(yù)測(cè)值最大的路哥桥，像上述包含商品A預(yù)測(cè)值大于不包含商品A的情況辙浑，因此，我們暫時(shí)選擇包含商品A拟糕，下一步就可以考慮是否包含商品B判呕，計(jì)算方法類(lèi)似
更換路線條件:
按照上述方法就為沿著一條路線不斷前進(jìn)且在岔路口選擇是否包含某一商品提供了一種判斷方法，那么什么情況得更換線路呢送滞？
- 重量超標(biāo)的情況侠草，本例中，假如每一條路線重量超過(guò)了10犁嗅，則該路走不通了边涕，必須切換到當(dāng)前預(yù)測(cè)價(jià)值最大的那條線路。
- 預(yù)測(cè)值下降嚴(yán)重，已經(jīng)小于另一條線路上的預(yù)測(cè)值功蜓，這是應(yīng)更換到那條預(yù)測(cè)值大的線路上园爷，也就是說(shuō)時(shí)刻走預(yù)測(cè)值最大的那條線路
結(jié)束條件:
-
每一件商品都考慮到了，如何此時(shí)還是最優(yōu)的情況式撼，那么這條線路就一定是最優(yōu)的情況童社，如本例中就是包含商品A，B著隆，C扰楼，不包含商品D,最大價(jià)值是235
python代碼
"""
Created on Mon Jan 7 21:57:42 2019
@author: WAY
"""
from copy import copy,deepcopy
class Item:
def __init__(self,w,v):
self.w = w
self.v = v
self.r = v/w
def __lt__(self,other):
return self.r<other.r
class Node:
def __init__(self):
self.layer = -1
self.info=[]
self.optimum_value = -1
self.total_weight=0
def __lt__(self,other):
return self.optimum_value<other.optimum_value
class Knapsack:
def __init__(self,N,maxweight):
self.N=N
self.items = []
self.max_weight = maxweight
self.max_value = 0
self.quene = []
def add_item(self,item):
self.items.append(item)
def sort_item(self):
self.items.sort()
self.items.reverse()
def calculate_matrix_value(self,node):
weight = 0
value = 0
for i in node.info:
weight += i.w
value += i.v
if weight>self.max_weight:
node.optimum_value = -1
return
node.total_weight=weight
for j in range(node.layer+1,self.N):
if weight + self.items[j].w <= self.max_weight:
weight += self.items[j].w
value += self.items[j].v
else:
value += self.items[j].r*(self.max_weight-weight)
break
node.optimum_value = value
def knapsack(self):
node = Node()
self.calculate_matrix_value(node)
self.max_value = node.optimum_value
self.quene.append(node)
panduan = 0
while self.quene:
if panduan == 0:
node = self.quene.pop()
panduan=1
node_L = deepcopy(node)
node_L.layer += 1
node_L.info.append(self.items[node_L.layer])
self.calculate_matrix_value(node_L)
if node_L.optimum_value>0 and node_L.optimum_value <=self.max_value:
self.quene.append(node_L)
node_R = deepcopy(node)
node_R.layer += 1
self.calculate_matrix_value(node_R)
if node_R.optimum_value>0 and node_R.optimum_value <=self.max_value:
self.quene.append(node_R)
self.quene.sort()
node = self.quene.pop()
if node.layer == 3:
break
return node
def main():
item1 = Item(2,40)
item2 = Item(3.14,50)
item3 = Item(1.98,100)
item4 = Item(5,95)
k = Knapsack(4,10)
k.add_item(item1)
k.add_item(item2)
k.add_item(item3)
k.add_item(item4)
k.sort_item()
nn = k.knapsack()
print(nn.optimum_value)
print(nn.total_weight)
for i in nn.info:
print(i.w)
if __name__ == "__main__":
main()
