python递归解决0-1背包问题，python递归0-1背包,#coding:utf-

python递归解决0-1背包问题，python递归0-1背包,#coding:utf-

#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]