头歌05-子集树实验-01背包

def knapsack_backtrack(n, G, weights, values):
    def backtrack(i, current_weight, current_value, current_items):
        nonlocal max_value
        nonlocal max_solutions
        if i == n:
            if current_value > max_value:
                max_value = current_value
                max_solutions = [list(current_items)]
            elif current_value == max_value:
                max_solutions.append(list(current_items))
            return

        # 不选择当前物品
        backtrack(i + 1, current_weight, current_value, current_items)

        # 选择当前物品
        if current_weight + weights[i] <= G:
            current_items.append(i + 1)
            backtrack(i + 1, current_weight +
                      weights[i], current_value + values[i], current_items)
            current_items.pop()

    max_value = 0
    max_solutions = []
    backtrack(0, 0, 0, [])
    return max_value, max_solutions


# 输入
n, G = map(int, input().split())
weights = list(map(int, input().split()))
values = list(map(int, input().split()))

# 计算并输出最大价值和方案
max_value, solutions = knapsack_backtrack(n, G, weights, values)
print("最大价值是{}".format(max_value))
print("最大价值共有{}种选择方案,分别是:".format(len(solutions)))
for solution in solutions:
    print("选择第{}个物品".format(' '.join(map(str, solution))))