0/1 Knapsack动态规划自顶向下实现输出错误排查求助

你的问题出在动态规划转移逻辑的两处参数误用：

• 状态判断条件错误：你用物品重量和背包总容量w做比较，正确逻辑需要和当前遍历的子背包容量j比较，即改为if(weight[i-1] <= j)
• 转移方程索引错误：选择装入当前物品时，剩余容量应该用当前子容量j减去物品重量，不是用总容量w，即转移式修改为max(value[i-1]+t[i-1][j-weight[i-1]], t[i-1][j])

你错误用总容量w替换了所有子容量j，相当于每一步计算都直接套用满容量的状态，导致价值被重复累加，才会得到280的错误结果。

修复后完整代码 #

#include<bits/stdc++.h>
using namespace std;

void knapsack(vector<int>& weight, vector<int>& value, int w, int n){
    
    vector<vector<int>> t;
    for(int i=0;i<n+1;++i){
        vector<int> temp;
        for(int j=0;j<w+1;++j){
                int x =0;
                temp.push_back(x);
        }
        t.push_back(temp);
        temp.clear();
    }
    
    for(int i=1;i<n+1;++i){
        for(int j=1;j<w+1;++j){
            if(weight[i-1]<=j){
                t[i][j] = max(value[i-1]+t[i-1][j-weight[i-1]], t[i-1][j]);
                
            }
            else{
               t[i][j] = t[i-1][j];
               
            }
        }
    }
    cout<<"Max Profit: "<<t[n][w];
}

int main(){
    
    int n;
    int w;//Total weight of knapsack
    cin>>n;
    cin>>w;
    
    vector<int> weight;
    vector<int> value;
    
    for(int i=0;i<n;++i){
        int x;
        cin>>x;
        weight.push_back(x);
    }
    for(int i=0;i<n;++i){
        int x;
        cin>>x;
        value.push_back(x);
    }
    
  knapsack(weight,value,w,n);
}

测试你给出的用例：重量数组[10,20,30]，价值数组[60,100,120]，背包最大承重50，运行后输出为Max Profit: 220，符合预期结果。

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