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

python递归解决0-1背包问题

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

python递归解决0-1背包问题

#coding:utf-8
#递归实现的背包算法
#背包大小
bag=10
#物品大小清单
list=[5,9,8,2,4,1,6,7,3]
#预处理:从小到大排序
list.sort()
#求背包组合
def getb(B,L):
    #本次查找结果
    r=[]
    #取最小数
    for k in range(0,len(L)):
        #去掉前面的k-1个元素,组成sL列表,在此基础上查找,以免出现重复的组合
        sL=L[k:]
        if len(sL)<2:
            break
        #取第一个元素(列表中的最小元素)
        x=sL[0]
        #背包的剩余空间
        e=B-x
        #查找e是否在表中,从sL[1]开始查找
        for i in range(1,len(sL)):
            #找到等于e的值,存入这组结果
            if sL[i]==e:
                r.append([x,sL[i]])
                break
            elif sL[i]>e:
                break
        #取子列表,sL[i]>=e的情况取中间的片段(减少不必要的开销),否则取从1开始的全部片段
        if sL[i]>=e:
            sL=sL[1:i]
        else:
            sL=sL[1:]
        #继续在子列表sL[1:]中以e为背包大小求组合
        sr=getb(e,sL)
        #查找的子结果处理后添加到结果列表中
        for j in sr:
            j.insert(0,x)
        r.extend(sr)
    #返回本次查找结果
    return r
#计算结果,输出结果
result=getb(bag,list)
for i in result:
    print i

输出结果:[1,&nbsp9][1,&nbsp2,&nbsp7][1,&nbsp2,&nbsp3,&nbsp4][1,&nbsp3,&nbsp6][1,&nbsp4,&nbsp5][2,&nbsp8][2,&nbsp3,&nbsp5][3,&nbsp7][4,&nbsp6]


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