注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

用python解决0-1背包问题代码

python 水墨上仙 1135次浏览 已收录 手机上查看

女朋友的单位需要解一个背包问题,说白了就是算票。通过有限的票,凑出最接近一个数字的组合来。 这个是经典问题,不过票数比较多,我本来用随机划分,然后一次优化一步的随机算法,凑出一个接近的数字。这样算法比较快,不过不是很准。 女朋友领导发话了,时间长点可以接受,但是最好准点。 照做吧,幸好这个算法算100张票子也就是10秒不到,这还是mini-itx。出处:http://shell909090.com/blog/2011/04/python%E8%A7%A30-1%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp照做吧,幸好这个算法算100张票子也就是10秒不到,这还是mini-itx。&nbsp&nbsp&nbsp&nbsp下面上算法,具体算法猛击这里(http://www.oiers.cn/pack/Index.html&nbsp)和这里(http://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98&nbsp)。输入是数字列表和目标,输出是组合和误差。f[i]是目前为止,最大代价为i所能获得的最高收益,以及组合方式。numlist是二维数组,分别是代价和收益。

def resolv_dym(numlist, target):
    f = [[0, []] for i in xrange(0, target + 1)]
    for c, w in numlist:
        for v in xrange(target, c – 1, -1):
            if f[v - c][0] + w > f[v][0]:
                f[v][0] = f[v - c][0] + w
                f[v][1] = f[v - c][1] + [(c, w),]
    return f[target][1], float(abs(target – f[target][0]))
    

当然,在这个特例里面,代价和收益相等,所以下面是真实代码。

def resolv_dym(numlist, target):
    f = [[0, []] for i in xrange(0, target + 1)]
    for i in numlist:
        for v in xrange(target, i – 1, -1):
            if f[v - i][0] + i > f[v][0]:
                f[v][0] = f[v - i][0] + i
                f[v][1] = f[v - i][1] + [i,]
    return f[target][1], float(abs(target – f[target][0]))


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明用python解决0-1背包问题代码
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……