背包问题，一般可以用动态规划解决。当涉及到的物体数目比较多，填表法所需要的存储空间很大$O(nW)$，每次都以内存不足告终。
参考：
https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/
1.填表法：
def solve_it(input_data): # Modify this code to run your optimization algorithm # parse the input lines = input_data.split(' ') 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) +' ' # 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] = 0 for 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_count while(result[k,j] != 0): if result[k][j] > result[k][j-1]: k = k - items[j-1].weight taken[j-1] = 1 j = j - 1 else: j = j - 1 # prepare the solution in the specified output format output_data = str(value) + ' ' + str(0) + ' ' 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 import cmp_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 import cmp_to_key #自定义比较函数 def mycmp(item1, item2): if(item1.value*1.0/item1.weight > item2.value*1.0/item2.weight): #value/weight大的排前边 return -1 else: return 0 #关于python3的自定义比较函数用法 items.sort(key=cmp_to_key(lambda a, b : mycmp(a,b)))
2.2 用到了节点类：
#节点类 class Node: 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 = capacity def show(self): print(self.level , ",", self.curvalue, ",", self.room, "," , self.bestvalue) #所求的bound值 def bound(self, items): weight = 0 value = 0 if self.level == -1: for i in range(len(items)): if weight + items[i].weight <= self.capacity: value += items[i].value weight += items[i].weight else: value += (self.capacity - weight) * 1.0 / items[i].weight * items[i].value break else: value += self.curvalue weight += self.capacity - self.room for i in range(self.level+1, len(items), 1): if weight + items[i].weight <= self.capacity: value += items[i].value weight += items[i].weight else: value += (self.capacity - weight) * 1.0 / items[i].weight * items[i].value break return value
3. 深度优先的分支定界。用栈实现，未用递归。
def solve_it(input_data): # Modify this code to run your optimization algorithm # parse the input lines = input_data.split(' ') 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(lambda a, 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 = 0 while(len(stack) != 0): #弹出末尾的节点 t = stack.pop() v = Node(-1, 0, capacity, 0, empty, capacity) if t.level == -1: v.level = 0 if t.level == item_count-1: continue #not choose this item v.level = t.level + 1 v.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 + 1 v1.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] = 1 v1.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) + ' ' output_data += ' '.join(map(str, taken)) return output_data
4.总结
第一次做分支定界算法，总算解决了问题。第一遍写的实现问题百出，首先是bound的计算问题，当bound计算出错时，会发现树无法高效地剪枝(pruning)。导致程序一直运行。后来才发现是bound的计算错误。改正bug后，程序完成的时间都不到一分钟。