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

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]