最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
Python基于回溯法子集树模板解决0-1背包问题实例
时间:2017-09-08 编辑:猪哥 来源:一聚教程网
问题
给定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))
效果图
-
下一个: PHP实现常用文件上传
相关文章
- Golang ProtoBuf的基本语法详解 10-20
- Python识别MySQL中的冗余索引解析 10-20
- Python+Pygame绘制小球代码展示 10-18
- Python中的数据精度问题介绍 10-18
- Python随机值生成的常用方法介绍 10-18
- python3解压缩.gz文件分析 09-27