蛮力回溯法实现0-1背包问题返回结果与预期不符排查

核心逻辑错误 #

原代码的回溯终止条件存在严重逻辑漏洞：

• 终止判断if(i+1 >= len(items) or curr_weight + items[i+1][1] > max_weight)中，只要下一个物品重量超过当前剩余容量，就直接返回当前累计利润，完全跳过了「跳过当前装不下的物品，继续向后遍历其他可装入物品」的分支。
• 这种逻辑会导致大量合法的物品组合根本没有被遍历到：比如当遍历到某一个重量超标的物品时，后续所有重量更小、可以装入的物品都会被直接忽略，最终计算出的最大利润必然小于真实值。
• 额外的边界问题：初始递归从索引-1开始，额外增加了索引判断的复杂度，很容易引入边界判断错误。

修复方法 #

重构回溯逻辑，拆分终止条件和分支判断：

1. 仅当遍历完全部物品（索引超出物品列表范围）时，才返回当前累计利润作为候选最大值
2. 对每个遍历到的物品，固定计算「不选当前物品」的分支结果
3. 仅当当前物品重量加已装重量不超过背包最大承重时，再计算「选当前物品」的分支结果，和不选的结果取最大值返回

修复后的可运行代码如下：

items = [[44,92], [46,4], [90,43], [72,83], [91,84], [40,68], [75,92], [35,82], [8,6], [54,44], [78,32], [40,18], [77,56], [15,83], [61,25], [17,96], [75,70], [29,48], [75,14], [63,58]]
max_weight = 269

def knapsack_bruteforce(items, max_weight):
    def backtrack(i, curr_profit, curr_weight):
        # 所有物品遍历完成，返回当前累计利润
        if i >= len(items):
            return curr_profit
        # 分支1：不选当前第i个物品，直接遍历下一个
        max_profit = backtrack(i + 1, curr_profit, curr_weight)
        # 分支2：如果装得下，选当前第i个物品后再遍历下一个
        if curr_weight + items[i][1] <= max_weight:
            choose_profit = backtrack(i + 1, curr_profit + items[i][0], curr_weight + items[i][1])
            max_profit = max(max_profit, choose_profit)
        return max_profit
    # 从第0个物品开始递归，初始利润、载重均为0
    return backtrack(0, 0, 0)

验证结果 #

传入题目给出的物品列表和最大承重269调用修复后的函数，返回值为550，和预期结果完全一致。

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