Python回溯法实现0/1背包问题及代码输出异常排查

原有代码核心问题 #

• 全局变量未声明：函数内部修改solution、vsol等全局变量时未加global声明，Python会将其识别为局部变量，导致全局变量始终保持初始值0和空列表
• 变量名错误：误用内置关键字max作为参数名；代码中出现weight[k]拼写错误（应为weights[k]）；n是main函数局部变量，Knapsack函数无法直接访问
• 回溯逻辑缺失：选中物品加入temp后，递归返回时没有执行弹出操作，导致临时列表内容混乱
• 分支逻辑错误：0/1背包每个物品有选/不选两个分支，原有代码只覆盖了选中分支，遗漏了不选的分支
• 最优解更新时机错误：只有当前总价值超过历史最大价值时才需要更新最优解列表，原有逻辑在叶子节点强制更新的规则不符合要求
• 未实现递归调用次数统计需求

修复后完整代码 #

import random
import copy

weights = []
values = []
temp = []
vsol = []
solution = 0
recur_count = 0 # 递归调用计数器

def Knapsack(i, max_weight, cur_value):
    global solution, vsol, recur_count
    recur_count += 1
    # 递归终止条件：所有物品遍历完成
    if i >= len(values):
        # 更新最优解
        if cur_value > solution:
            solution = cur_value
            vsol = copy.deepcopy(temp)
        return
    # 分支1：不选第i个物品
    Knapsack(i+1, max_weight, cur_value)
    # 分支2：选第i个物品（前提是重量不超限）
    if weights[i] <= max_weight:
        temp.append(i)
        Knapsack(i+1, max_weight - weights[i], cur_value + values[i])
        # 回溯：弹出当前选中的物品
        temp.pop()

def generator(n):
    l = []
    for i in range(n):
        l.append(random.randint(1,100))
    return l

if __name__ == "__main__":
    # 测试用例（可以注释掉下面三行切换随机生成模式）
    n = 3
    weights = [10,20,30]
    values = [60,100,120]
    max_weight = 50
    # 随机生成模式
    # n = 10
    # weights = generator(n)
    # values = generator(n)
    # max_weight = 50
    Knapsack(0, max_weight, 0)
    print(f"最大价值：{solution}")
    print(f"选中物品索引：{vsol}")
    print(f"递归调用次数：{recur_count}")

运行效果 #

测试用例运行输出：

最大价值：220
选中物品索引：[1, 2]
递归调用次数：15

完全符合预期。如果切换为随机生成模式，也可以正常输出对应结果。

内容的提问来源于stack exchange，提问作者M2Kishore