分⽀定界法python_分⽀定界（Branchbound）算法
背包问题，⼀般可以⽤动态规划解决。当涉及到的物体数⽬⽐较多，填表法所需要的存储空间很⼤$O(nW)$，每次都以内存不⾜告终。参考：
1.填表法：
defsolve_it(input_data):#Modify this code to run your optimization algorithm
#par the input
lines = input_data.split('\n')
firstLine=lines[0].split()
item_count=int(firstLine[0])
capacity= int(firstLine[1])
items=[]for i in range(1, item_count+1):
line=lines[i]
parts=line.split()
items.append(Item(i-1, int(parts[0]), int(parts[1])))#print item information
#for i in range(0, len(items)):
#print str(items[i].index) + ',' + str(items[i].value) + ',' + str(items[i].weight) +'\n'
#a trivial greedy algorithm for filling the knapsack
#it takes items in-order until the knapsack is full
value =0
weight=0
taken= [0]*len(items) #为1则表⽰选择了该物体
'''for item in items:
if weight + item.weight <= capacity:
taken[item.index] = 1
value += item.value
weight += item.weight'''result= np.zeros([capacity+1, item_count+1]) #表的⼤⼩为n*W,n为物体数⽬，W为包的容量
#result[k][0] = 0 for all k
for i in range(0, capacity+1):
result[i][0]=0for i in range(0, item_count+1):
result[0][i]=0#填表法
for k in range(1, capacity+1):for j in range(1, item_count+1): #第j件物品其索引值为j-1
if k-items[j-1].weight >=0:
result[k][j]= max([result[k][j-1], result[k-items[j-1].weight][j-1] + items[j-1].value])el:
result[k][j]= result[k][j-1]
value=int(result[capacity][item_count])
out_to_csv(result)#根据表寻找最优解的路径
k =capacity
j=item_countwhile(result[k,j] !=0):if result[k][j] > result[k][j-1]:
k= k - items[j-1].weight
taken[j-1] = 1j= j - 1
el:
j= j - 1
#prepare the solution in the specified output format
output_data = str(value) + ' ' + str(0) + '\n'output_data+= ' '.join(map(str, taken))return output_data
填表法在物体数⽬较⼩的时候可以解决，单所需表的存储空间⽐较⼤的时候开始报错。
故选择了分⽀定界算法。
2. 关于python3中⾃定义⽐较函数的⽤法：
参考⾃：/archives/Python3-%E6%89%BE%E5%9B%9Esort-
%E4%B8%AD%E6%B6%88%E5%A4%B1%E7%9A%84cmp%E5%8F%82%E6%95%B0.html
from functools importcmp_to_key
nums= [1, 3, 2, 4]
nums.sort(key=cmp_to_key(lambda a, b: a -b))print(nums) #[1, 2, 3, 4]
2.1 我的⾃定义⽐较函数：
from functools importcmp_to_key#⾃定义⽐较函数
defmycmp(item1, item2):if(item1.value*1.0/item1.weight > item2.value*1.0/item2.weight): #value/weight⼤的排前边return -1
el:return0#关于python3的⾃定义⽐较函数⽤法
items.sort(key=cmp_to_key(lambda a, b : mycmp(a,b)))
2.2 ⽤到了节点类：
#节点类
classNode:def __init__(lf, level, curvalue, room, bestvalue, taken, capacity): #成员变量
lf.level =level
lf.curvalue=curvalue
<=room
lf.bestvalue=bestvalue
lf.path=taken
lf.capacity=capacitydefshow(lf):print(lf.level , ",", lf.curvalue, ",", lf.room, ",", lf.bestvalue)#所求的bound值孙子兵法下载
defbound(lf, items):
weight=0
value=0if lf.level == -1:for i inrange(len(items)):if weight + items[i].weight <=lf.capacity:
value+=items[i].value
weight+=items[i].weightel:
value+= (lf.capacity - weight) * 1.0 / items[i].weight *items[i].valuebreak
el:
value+=lf.curvalue
weight+= lf.capacity -lf.roomfor i in range(lf.level+1, len(items), 1):if weight + items[i].weight <=lf.capacity: value+=items[i].value
weight+=items[i].weightel:
value+= (lf.capacity - weight) * 1.0 / items[i].weight *items[i].valuebreak
return value
3. 深度优先的分⽀定界。⽤栈实现，未⽤递归。
defsolve_it(input_data):#Modify this code to run your optimization algorithm
#par the input
lines = input_data.split('\n')
firstLine=lines[0].split()
item_count= int(firstLine[0]) #物体数⽬
gay是什么capacity = int(firstLine[1]) #背包容量
items =[]for i in range(1, item_count+1):
line=lines[i]
我的最爱英文
parts=line.split()
items.append(Item(i-1, int(parts[0]), int(parts[1]))) #物体初始化after effect
value=0
weight=0
taken= [0]*len(items)
empty= [0]*len(items)#关于python3的⾃定义⽐较函数⽤法
items.sort(key=cmp_to_key(lambdaa, b : mycmp(a,b)))#for item in items:
#print (str(item.index) + "," + str(item.value) + "," + str(item.weight))
stack= [] #深度优先⽤栈实现，python中list代替
u = Node(-1, 0, capacity, 0, empty, capacity)
temp=u.bound(items)
pleau.bestvalue=temp#print("curvalue:", u.curvalue)
#print("bound:", u.bestvalue)
stack.append(u)
max_profit=0while(len(stack) !=0):#弹出末尾的节点
t =stack.pop()
好看的法语电影
v= Node(-1, 0, capacity, 0, empty, capacity)if t.level == -1:
v.level=0if t.level == item_count-1:continue
#not choo this item
v.level = t.level + 1v.
v.curvalue=t.curvalue
v.bestvalue=v.bound(items)
this timev.path= py() #注意Python中list为引⽤，故不能直接赋值，⽽是⽤copy()⽅法
if v.bestvalue >max_profit:
stack.append(v)if v.level == item_count -1:
max_profit= v.curvalue #保留最⼤profit
taken = v.path #保留最优解
gpa怎么算#choo this item
suits第二季v1 = Node(-1, 0, capacity, 0, empty, capacity)
v1.level= t.level + = t.room -items[v1.level].weight
v1.curvalue= t.curvalue +items[v1.level].value#print("curvalue:", v1.curvalue)
#copy(), 不能直接赋值，因为都是引⽤
v1.path =py()
v1.path[items[v1.level].index]= 1v1.bestvalue=t.bestvalue#print("v1.path:", v1.path)
if (v1.room >= 0) and (v1.bestvalue >max_profit):#print(taken)
#满⾜则加⼊stack
stack.append(v1)if v1.level == item_count-1:
max_profit= v1.curvalue #保留最⼤profit
taken = v1.path #保留最优解集
#print(taken)mouth是什么意思
value =max_profit#prepare the solution in the specified output format
output_data = str(value) + ' ' + str(0) + '\n'output_data+= ' '.join(map(str, taken))return output_data
4.总结
第⼀次做分⽀定界算法，总算解决了问题。第⼀遍写的实现问题百出，⾸先是bound的计算问题，当bound计算出错时，会发现树⽆法⾼效地剪枝(pruning)。导致程序⼀直运⾏。后来才发现是bound的计算错误。改正bug后，程序完成的时间都不到⼀分钟。
