如何修正递归实现的01背包问题中的最优解数组y？

问题分析 #

你这段递归代码能算出正确的最优值15，但输出的选择数组y=[1,1,0,0,0]明显不对——这个组合的总价值只有9，和最优值完全不匹配。问题出在递归过程中对y数组的修改逻辑上：

当计算「不选当前物品（tmp1）」和「选当前物品（tmp2）」时，两次递归调用会直接修改同一个y数组。计算完tmp1后，再计算tmp2的过程会覆盖掉tmp1递归时对后续元素的赋值，最后y数组存的是最后一次递归（tmp2）的路径，而非真正的最优解路径。

修正代码 #

解决思路是在计算tmp2前，先备份tmp1对应的后续元素状态，等比较完tmp1和tmp2后，再根据选择恢复对应的状态：

import numpy as np

def recurseKnapsack(w, v, i, j, c, n, y):
    if i == n - 1:
        if j < w[i]:
            optvalue = 0
            y[i] = 0
        else:
            optvalue = v[i]
            y[i] = 1
        return optvalue

    if j < w[i]:
        y[i] = 0
        optvalue = recurseKnapsack(w, v, i+1, j, c, n, y)
    else:
        # 备份i+1及之后的数组状态，避免tmp2递归覆盖tmp1的结果
        y_backup = y[i+1:].copy()
        tmp1 = recurseKnapsack(w, v, i+1, j, c, n, y)
        # 恢复备份，再计算选当前物品的情况
        y[i+1:] = y_backup
        tmp2 = recurseKnapsack(w, v, i+1, j - w[i], c, n, y) + v[i]
        
        if tmp1 > tmp2:
            optvalue = tmp1
            # 选不拿当前物品，恢复tmp1对应的后续状态
            y[i+1:] = y_backup
            y[i] = 0
        else:
            optvalue = tmp2
            # 选拿当前物品，保留tmp2的后续状态
            y[i] = 1

    return optvalue


w  = [2, 2, 6, 5, 4]
v  = [6, 3, 5, 4, 6]
c = 10

y = np.zeros_like(w)
optvalue = recurseKnapsack(w, v, 0, c, c, len(w), y)
print("optValue", optvalue, y)

修正后输出 #

optValue 15 [1 1 0 0 1]

这个结果对应的是选择第0、1、4个物品，总重量2+2+4=8，总价值6+3+6=15，完全匹配最优值。

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