返回顶部

收藏

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, 9] [1, 2, 7] [1, 2, 3, 4] [1, 3, 6] [1, 4, 5] [2, 8] [2, 3, 5] [3, 7] [4, 6]

标签:背包问题,算法,python

收藏

0人收藏

支持

1

反对

0

发表评论