Python基于回溯法子集树模板解决0-1背包问题实例
作者:罗兵 发布时间:2021-02-02 08:57:54
标签:Python,回溯法
本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题。分享给大家供大家参考,具体如下:
问题
给定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 # 最佳解
# 冲突检测
def conflict(k):
global bag, w, c
# bag内的前k个物品已超重,则冲突
if sum([y[0] for y in filter(lambda x:x[1]==1, zip(w[:k+1], bag[:k+1]))]) > c:
return True
return False
# 套用子集树模板
def backpack(k): # 到达第k个物品
global bag, maxv, maxw, bestbag
if k==n: # 超出最后一个物品,判断结果是否最优
cv = get_a_pack_value(bag)
cw = get_a_pack_weight(bag)
if cv > maxv : # 价值大的优先
maxv = cv
bestbag = bag[:]
if cv == maxv and cw < maxw: # 价值相同,重量轻的优先
maxw = cw
bestbag = bag[:]
else:
for i in [1,0]: # 遍历两种状态 [选取1, 不选取0]
bag[k] = i # 因为解的长度是固定的
if not conflict(k): # 剪枝
backpack(k+1)
# 根据一个解bag,计算重量
def get_a_pack_weight(bag):
global w
return sum([y[0] for y in filter(lambda x:x[1]==1, zip(w, bag))])
# 根据一个解bag,计算价值
def get_a_pack_value(bag):
global v
return sum([y[0] for y in filter(lambda x:x[1]==1, zip(v, bag))])
# 测试
backpack(0)
print(bestbag, get_a_pack_value(bestbag))
效果图
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/hhh5460/p/6920056.html
0
投稿
猜你喜欢
- 1.介绍在 Golang 语言项目开发中,经常会遇到数据排序问题。Golang 语言标准库 sort 包,为我们提供了数据排序的功能,我们可
- 如何用通过Web访问OLAP数据? <% Set Conn=Server.CreateObject(″A
- 一般iis中比较简单,iis6如下图所示即可:很多购买虚拟主机空间的用户,如果空间商提供了在线管理程序,也可以实现。具体的看下帮助即可。需要
- 本文实例讲述了PHP实现执行外部程序的方法。分享给大家供大家参考,具体如下:在一些特殊情况下,会使用PHP调用外部程序执行,比如:调用she
- 阅读上一篇:FrontPage2002简明教程六:图片库 虽然FrontPage已经给我们提供了很多面很强大的所见即所得的工具,但是随着HT
- Internet Explorer 8 Beta 测试了一年多之后,今天,IE8 终于发布了。它绝对好过 IE7,还有一些不错的新功能,如
- 本文介绍ThinkPHP的limit()方法的用法。limit方法可以用于对数据库操作的结果进行取指定范围的条数。即相当于是在mysql查询
- xmlhttp,IE不支持overrideMimeType()方法,即使是IE7。 // Mozilla/Safari/
- 如果你是个赛车手,并且按一下按钮就能够立即更换引擎而不需要把车开到车库里去换,那会是什么感觉呢?MySQL数据库为开发人员所做的就好像是按按
- 1、下载mysql-python官网地址:http://sourceforge.net/projects/mysql-python/2、安装
- 需求:用SQL语句随机从数据库中随机取N条数据。以前不太清楚SQL语句可以直接随机取数据今天查了一下,发现有两个随机函数: newid()
- 代码如下:'===================================== '转换内容,防止意外 '==
- 监控中,通常要使用图片更直观的看出集群的运行状况。以下是一个简单的demo,通过rrdtool生成动态的图片。Python3, tornad
- '-----------------------------------------------------------
- 如果我们想对一个表的每一行做出比较复杂的操作,大多会想到用游标,本文中,我们将换一种思路,用SQL Server 2005中的新函数ROW_
- 搞前端应该对语义化并不陌生,每天都在说语义化,可什么是语义化,语义化究竟能给我们带来什么好处?参加web标准交流会的时候我向各位同学提出了我
- 1 、据说python3就没有这个问题了2 、u'字符串' 代表是unicode格式的数据,路径最好写成这个格式,别直接跟字
- 初学ASP,程序是能勉强写出来了,但若每进行一次网站页面的改版,所有的源程序都将进行一次移植手术。为此所耗费的人力精力不计其数,甚至一不小心
- php二维数组排序测试数据 $arr = [
- 首先要把php_iconv.dll和inconv.dll COPY到c:\winnt\system32下,直接上代码:<?define