国外优质网站/长春关键词优化报价
背包问题，一般可以用动态规划解决。当涉及到的物体数目比较多，填表法所需要的存储空间很大$O(nW)$，每次都以内存不足告终。
参考：
https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/
1.填表法：
defsolve_it(input_data):#Modify this code to run your optimization algorithm
#parse 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])else:
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
else:
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中自定义比较函数的用法：
参考自：https://www.polarxiong.com/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
else:return0#关于python3的自定义比较函数用法
items.sort(key=cmp_to_key(lambda a, b : mycmp(a,b)))
2.2 用到了节点类：
#节点类
classNode:def __init__(self, level, curvalue, room, bestvalue, taken, capacity): #成员变量
self.level =level
self.curvalue=curvalue
self.room=room
self.bestvalue=bestvalue
self.path=taken
self.capacity=capacitydefshow(self):print(self.level , ",", self.curvalue, ",", self.room, ",", self.bestvalue)#所求的bound值
defbound(self, items):
weight=0
value=0if self.level == -1:for i inrange(len(items)):if weight + items[i].weight <=self.capacity:
value+=items[i].value
weight+=items[i].weightelse:
value+= (self.capacity - weight) * 1.0 / items[i].weight *items[i].valuebreak
else:
value+=self.curvalue
weight+= self.capacity -self.roomfor i in range(self.level+1, len(items), 1):if weight + items[i].weight <=self.capacity:
value+=items[i].value
weight+=items[i].weightelse:
value+= (self.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
#parse 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]))) #物体初始化
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)
u.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 choose this item
v.level = t.level + 1v.room=t.room
v.curvalue=t.curvalue
v.bestvalue=v.bound(items)
v.path= t.path.copy() #注意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 #保留最优解
#choose this item
v1 = Node(-1, 0, capacity, 0, empty, capacity)
v1.level= t.level + 1v1.room= t.room -items[v1.level].weight
v1.curvalue= t.curvalue +items[v1.level].value#print("curvalue:", v1.curvalue)
#copy(), 不能直接赋值，因为都是引用
v1.path =t.path.copy()
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)
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后，程序完成的时间都不到一分钟。