问题
给定N个物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得放入背包的物品的总价值为最大？
分析
显然，放入背包的物品，是N个物品的所有子集的其中之一。N个物品中每一个物品，都有选择、不选择两种状态。因此，只需要对每一个物品的这两种状态进行遍历。
解是一个长度固定的N元0,1数组。
套用回溯法子集树模板，做起来不要太爽！！！
代码
"""0-1背包问题"""
n=3 # 物品数量
c=30 # 包的载重量
w=[20,15,15]# 物品重量
v=[45,25,25]# 物品价值
maxw=0# 合条件的能装载的最大重量
maxv=0# 合条件的能装载的最大价值
bag=[0,0,0]# 一个解（n元0-1数组）长度固定为n
bags=[] # 一组解
bestbag=None# 最佳解
# 冲突检测
defconflict(k):
globalbag, w, c
# bag内的前k个物品已超重，则冲突
ifsum([y[0]foryinfilter(lambdax:x[1]==1,zip(w[:k+1], bag[:k+1]))]) > c:
returnTrue
returnFalse
# 套用子集树模板
defbackpack(k):# 到达第k个物品
globalbag, maxv, maxw, bestbag
ifk==n:# 超出最后一个物品，判断结果是否最优
cv=get_a_pack_value(bag)
cw=get_a_pack_weight(bag)
ifcv > maxv :# 价值大的优先
maxv=cv
bestbag=bag[:]
ifcv==maxvandcw < maxw:# 价值相同，重量轻的优先
maxw=cw
bestbag=bag[:]
else:
foriin[1,0]:# 遍历两种状态 [选取1, 不选取0]
bag[k]=i# 因为解的长度是固定的
ifnotconflict(k):# 剪枝
backpack(k+1)
# 根据一个解bag，计算重量
defget_a_pack_weight(bag):
globalw
returnsum([y[0]foryinfilter(lambdax:x[1]==1,zip(w, bag))])
# 根据一个解bag，计算价值
defget_a_pack_value(bag):
globalv
returnsum([y[0]foryinfilter(lambdax:x[1]==1,zip(v, bag))])
# 测试
backpack(0)
print(bestbag, get_a_pack_value(bestbag))
效果图
【python怎么读】Python基于回溯法子集树模板解决0-1背包问题实例
http://m.bbyears.com/jiaocheng/136196.html
推荐访问:python教程 python能做什么