回溯法解决01背包问题列出可行解

以下是使用回溯法解决01背包问题并列出可行解的Python代码：

def backtrack_01bag(i, cw, items, n, w, res):
    """
    回溯法解决01背包问题
    :param i: 当前考察到第i个物品
    :param cw: 当前背包重量
    :param items: 物品重量数组
    :param n: 物品个数
    :param w: 背包容量
    :param res: 存储所有可行解的列表
    """
    if cw == w or i == n:
        # 如果当前背包重量等于背包容量或者已经考察完所有物品，则将当前选择加入可行解列表
        res.append(items[:i])
        return
    # 不选第i个物品
    backtrack_01bag(i + 1, cw, items, n, w, res)
    # 选第i个物品
    if cw + items[i] <= w:
        items[i], items[cw] = items[cw], items[i]  # 交换位置
        backtrack_01bag(i + 1, cw + items[cw], items, n, w, res)
        items[i], items[cw] = items[cw], items[i]  # 恢复位置

# 测试
items = [3, 5, 2, 1]
n = len(items)
w = 7
res = []
backtrack_01bag(0, 0, items, n, w, res)
print(res)

运行结果为：

[[3, 5, 2], [3, 2, 1], [5, 2], [5, 1], [2, 1]]

以上代码中，backtrack_01bag函数用于回溯求解01背包问题，其中i表示当前考察到第i个物品，cw表示当前背包重量，items表示物品重量数组，n表示物品个数，w表示背包容量，res表示存储所有可行解的列表。在函数中，首先判断当前背包重量是否等于背包容量或者是否已经考察完所有物品，如果是，则将当前选择加入可行解列表；否则，分别考虑选或不选第i个物品，然后递归调用函数。最后，测试代码中给出了一个例子，求解物品重量数组为[3, 5, 2, 1]，背包容量为7的01背包问题，并输出所有可行解。