回溯法实现0/1背包问题输出错误，求代码修正方案

问题背景 #

采用回溯法（状态空间树）实现0/1背包问题时，测试用例2输出结果不符合预期，需修正代码使其正确运行。相关参数定义：

• capacity：背包总容量
• cargo_number：物品数量
• size：各物品重量数组
• profit：各物品价值数组

测试用例 #

测试用例1（结果正确） #

输入：

16
4
2 5 10 5
40 30 50 10

输出：90

测试用例2（结果错误） #

输入：

10
5
7 2 10 2 4
46 19 30 49 11

预期输出：95，实际输出：98

现有错误代码 #

from typing import List


class Solution:
    def fractional_knapsack(self, n: int, size: List[int], profit: List[int], left_capacity: int):
        if left_capacity <= 0:
            return 0
        # sort profit and size in descending order
        sorted_index = sorted(range(n), key=lambda i: profit[i] / size[i], reverse=True)
        sorted_size = [size[i] for i in sorted_index]
        sorted_profit = [profit[i] for i in sorted_index]

        estimated_profit = 0
        for i in range(n):
            if sorted_size[i] <= left_capacity:
                estimated_profit += sorted_profit[i]
                left_capacity -= sorted_size[i]
            else:
                estimated_profit += sorted_profit[i] * (left_capacity / sorted_size[i])
                break
        return estimated_profit

    def knapsack(self, i, left_capacity):
        global max_profit
        if i >= cargo_number or left_capacity <= 0:
            return

        current_s = sum(size[i] for i in range(cargo_number) if x[i] == 1)  # sum of current size
        current_p = sum(profit[i] for i in range(cargo_number) if x[i] == 1)  # sum of current profit

        if current_s + size[i] <= left_capacity:
            estimated_profit = self.fractional_knapsack(
                cargo_number - (i + 1),
                size[i + 1:],
                profit[i + 1:],
                left_capacity - size[i],
            )
            if current_p + profit[i] > max_profit:  # renew max_profit
                max_profit = current_p + profit[i]
            x[i] = 1  # if item is selected
            self.knapsack(i + 1, left_capacity - size[i])  #

        estimated_profit = fractional_knapsack(
        cargo_number - (i + 1), size[i + 1:], profit[i + 1:], left_capacity
    )
        if current_p + estimated_profit > max_profit:
            x[i] = 0  # if item is not selected
            self.knapsack(i + 1, left_capacity)


capacity = int(input())
cargo_number = int(input())
size = list(map(int, input().split()))
profit = list(map(int, input().split()))

x = [0] * cargo_number  # if x[i] == 1, then i-th item is selected, otherwise not
max_profit = 0

solution = Solution()
solution.knapsack(0, capacity)
print(max_profit)

问题分析与修改方案 #

核心问题点 #

1. 全局状态未回溯：使用全局变量x记录物品选择状态，但递归返回后未重置x[i]，导致后续分支状态混乱。
2. 剪枝逻辑错误：调用fractional_knapsack时遗漏self前缀，且剪枝判断顺序颠倒——应先判断预估利润是否可能超越当前最大值，再决定是否递归。
3. 累计值计算低效：每次递归遍历所有物品计算当前重量和价值，冗余且易出错。
4. 最大值更新不完整：仅在选择物品时更新max_profit，未处理递归结束时的最终状态校验。

修改后的代码 #

from typing import List


class Solution:
    def fractional_knapsack(self, n: int, size: List[int], profit: List[int], left_capacity: int) -> float:
        if left_capacity <= 0:
            return 0.0
        # 按单位价值降序排序物品
        sorted_items = sorted(zip(size, profit), key=lambda item: item[1]/item[0], reverse=True)
        estimated = 0.0
        remaining = left_capacity
        for s, p in sorted_items:
            if s <= remaining:
                estimated += p
                remaining -= s
            else:
                estimated += p * (remaining / s)
                break
        return estimated

    def knapsack(self, i: int, left_capacity: int, current_weight: int, current_profit: int):
        global max_profit
        # 递归终止：处理完所有物品时更新最大值
        if i >= cargo_number:
            if current_profit > max_profit:
                max_profit = current_profit
            return
        
        # 剪枝：预估利润无法超越当前最大值，直接返回
        estimated = current_profit + self.fractional_knapsack(
            cargo_number - i - 1,
            size[i+1:],
            profit[i+1:],
            left_capacity
        )
        if estimated <= max_profit:
            return
        
        # 分支1：选择第i个物品（容量足够时）
        if current_weight + size[i] <= left_capacity:
            self.knapsack(i+1, left_capacity - size[i], current_weight + size[i], current_profit + profit[i])
        
        # 分支2：不选择第i个物品
        self.knapsack(i+1, left_capacity, current_weight, current_profit)


capacity = int(input())
cargo_number = int(input())
size = list(map(int, input().split()))
profit = list(map(int, input().split()))

max_profit = 0

solution = Solution()
solution.knapsack(0, capacity, 0, 0)
print(max_profit)

关键修改说明 #

1. 移除全局状态变量：通过递归参数current_weight和current_profit传递累计值，避免状态混乱，无需回溯重置。
2. 修正剪枝逻辑：先计算当前路径的预估最大利润，若无法超过max_profit则直接剪枝，减少无效递归。
3. 正确调用成员方法：调用fractional_knapsack时添加self.前缀，解决未定义错误。
4. 完善终止条件：递归到所有物品处理完毕时，校验并更新max_profit，确保最终状态被正确计算。
5. 优化分数背包计算：简化排序逻辑，直接按单位价值排序物品，提升代码可读性。

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