0-1背包递归函数正确性校验及top down实现改写

我编写了一个0-1背包问题的递归函数，目前尝试将其转换为top down（自顶向下记忆化递归）版本，有两个疑问：

• 当前编写的递归函数逻辑是否正确？
• 能否协助我将其改写为标准top down实现？

原有实现代码如下：

# with memoization - assuming n constraint is 100 and size is 1000
t = [[-1] * 200 for i in range(200)]


def find_max_profit(final_arr, w_arr, v_arr, n):
      if not w_arr:
        return sum(final_arr)
      if sum(final_arr) + w_arr[0] > n:
        return sum(final_arr)

      if t[len(w_arr)][n] != -1:
        return t[len(w_arr)][n]

      t[len(w_arr)][n] = max(find_max_profit(final_arr + [v_arr[0]], w_arr[1:], v_arr[1:], n),
                           find_max_profit(final_arr, w_arr[1:], v_arr[1:], n))
      return t[len(w_arr)][n]

原有递归逻辑的问题 #

你的代码逻辑存在4个核心错误，无法得到正确结果：

1. 状态定义和记忆化不匹配：记忆化数组t只记录了「剩余物品数量」和「背包总容量」两个维度，但函数返回值依赖final_arr里累计的已选价值总和。相同剩余物品数、相同背包总容量下，可能对应多种已选物品的组合，已用容量、已获价值都不一样，直接复用记忆化结果会出现计算错误。
2. 剪枝逻辑错误：当判断当前物品装不下时，直接返回sum(final_arr)终止递归，相当于跳过了「不选当前物品、继续选后续物品」的分支，会导致最终结果偏小。
3. 参数设计低效：每次递归传递final_arr列表、对w_arr/v_arr做切片，额外增加了时间和空间开销，还需要反复计算sum(final_arr)，没有必要。
4. 记忆化数组大小不符合约束：你注释说明背包容量上限是1000，但初始化的t第二维长度只有200，当背包容量超过199时会触发索引越界。

标准Top Down实现 #

标准0-1背包自顶向下记忆化实现的核心是明确状态定义：dp[i][c]表示考虑第i个及之后的所有物品，背包剩余容量为c时，能获得的最大价值。这个状态只需要两个维度就能唯一确定，不需要记录已选物品的完整列表，记忆化可以直接生效。
修正后的代码如下：

# 记忆化数组：第一维对应物品索引上限100，第二维对应背包容量上限1000，和题目约束对齐
memo = [[-1] * 1001 for _ in range(101)]

def knapsack_top_down(weights, values, item_total, current_idx, remain_cap):
    # 递归边界：所有物品处理完，或者背包没有剩余容量，返回0价值
    if current_idx >= item_total or remain_cap <= 0:
        return 0
    
    # 命中记忆化缓存，直接返回预存结果
    if memo[current_idx][remain_cap] != -1:
        return memo[current_idx][remain_cap]
    
    # 分支1：不选当前物品，直接处理下一个物品
    not_take = knapsack_top_down(weights, values, item_total, current_idx + 1, remain_cap)
    
    # 分支2：选当前物品，仅当当前物品重量不超过剩余容量时可选
    take = 0
    if weights[current_idx] <= remain_cap:
        take = values[current_idx] + knapsack_top_down(weights, values, item_total, current_idx + 1, remain_cap - weights[current_idx])
    
    # 取两个分支的最大值存入缓存，返回结果
    memo[current_idx][remain_cap] = max(take, not_take)
    return memo[current_idx][remain_cap]


# 调用示例
if __name__ == "__main__":
    # 测试用例：重量[2,3,4,5]，价值[3,4,5,6]，背包容量8，正确最大价值为10（选3+5重量的物品，对应4+6价值）
    w = [2,3,4,5]
    v = [3,4,5,6]
    capacity = 8
    # 多组用例测试前需要重置记忆化数组，避免历史结果干扰
    for i in range(len(memo)):
        for j in range(len(memo[0])):
            memo[i][j] = -1
    print(knapsack_top_down(w, v, len(w), 0, capacity)) # 输出10

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