我的自上而下0-1背包DP解法出错，求帮助排查问题

我写的自上而下0-1背包动态规划解法在测试用例中失败，找不到问题所在，需要帮忙排查。

我的代码如下：

int fin(int i,int wt,int curprofit,vector<int>&A,vector<int>&B,int C,int n,vector<vector<int>>&dp)
{
    if(i==n)
        return curprofit;
    if(dp[i][wt]!=-1)
    return dp[i][wt];
    int ret=0;
    ret=max(ret,fin(i+1,wt,curprofit,A,B,C,n,dp));
    if(wt+B[i]<=C)
    {
        ret=max(ret,fin(i+1,wt+B[i],curprofit+A[i],A,B,C,n,dp));
    }
    return dp[i][wt]= ret;
}
int Solution::solve(vector<int> &A, vector<int> &B, int C) {
    int n=A.size();
    vector<vector<int>>dp(n+1,vector<int>(C+1,-1));
    return fin(0,0,0,A,B,C,n,dp);
}

问题分析 #

你的代码核心问题在于**curprofit参数与DP状态定义冲突**，导致记忆化存储的值不正确：

• dp[i][wt]的设计意图应该是「从第i个物品开始，已使用重量为wt时，能获得的最大利润」，但你在递归中传递了curprofit（之前累计的利润），并让dp[i][wt]存储了包含curprofit的结果。
• 当不同递归路径到达同一个(i, wt)状态时，curprofit可能不同（比如两条路径之前选的物品不同，累计利润不同），此时dp[i][wt]中存储的是第一次到达时的curprofit + 后续最大利润，但后续到达时用这个值会忽略当前路径的curprofit，导致结果错误。

修正方案 #

去掉curprofit参数，让dp[i][wt]直接表示当前状态下的最大利润：

int fin(int i, int wt, vector<int>& A, vector<int>& B, int C, int n, vector<vector<int>>& dp) {
    if (i == n)
        return 0; // 没有物品可选，利润为0
    if (dp[i][wt] != -1)
        return dp[i][wt];
    
    // 不选第i个物品的情况
    int skip = fin(i+1, wt, A, B, C, n, dp);
    // 选第i个物品的情况（如果重量允许）
    int take = 0;
    if (wt + B[i] <= C) {
        take = A[i] + fin(i+1, wt + B[i], A, B, C, n, dp);
    }
    
    // 存储当前状态的最大利润
    return dp[i][wt] = max(skip, take);
}

int Solution::solve(vector<int> &A, vector<int> &B, int C) {
    int n = A.size();
    vector<vector<int>> dp(n+1, vector<int>(C+1, -1));
    return fin(0, 0, A, B, C, n, dp);
}

修正逻辑说明 #

• 递归终止条件改为返回0：当处理完所有物品时，没有新增利润。
• 不选当前物品时，直接取后续状态的最大利润。
• 选当前物品时，将当前物品的利润A[i]加上后续状态的最大利润。
• dp[i][wt]存储的是当前状态（第i个物品、已用重量wt）下的最大利润，与之前的累计利润无关，确保记忆化的正确性。

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