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

"""
皮蛋编程(https://www.pidancode.com)
创建日期：2022/4/2
功能描述：python递归解决0-1背包问题
"""

# 递归实现的背包算法
# 背包大小
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)