C++实现0-1背包：用户输入数组结果错误、硬编码数组正确原因排查

问题原因 #

你代码的问题出在两个地方：

1. 使用了非标准C++语法的变长数组（VLA）
   C++标准不支持int a[n]、int b[n]这种用运行时变量n定义数组长度的写法，这是GCC的非标准扩展，内存分配逻辑不稳定，很容易出现数组取值异常、越界等问题，导致结果错误。你硬编码数组时长度是编译期固定值，所以不会触发这个问题。
2. 全局dp缓存没有每次调用前重置
   你使用的全局二维vectordp只会在程序启动时初始化一次为-1，每次调用knap函数前如果不重置dp的值，之前计算残留的缓存值会干扰本次的动态规划计算，直接导致结果错误。

修复方案 #

1. 将变长数组替换为C++标准的动态容器vector存储重量和价值数组
2. 每次调用knap函数前，将dp数组全部重置为初始值-1

修正后的完整代码示例 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> dp(1001, vector<int>(10001, -1));

int knap(int n, const vector<int>& wt, const vector<int>& price, int W){
    if(dp[n][W] != -1){
        return dp[n][W];
    }
    if(n == 0 || W == 0){
        return 0;
    }
    if(wt[n-1] <= W){
        return dp[n][W] = max((price[n-1] + knap(n-1, wt, price, W - wt[n-1])), knap(n-1, wt, price, W));
    }
    else{
        return dp[n][W] = knap(n-1, wt, price, W);
    }
}

int main(){
    int n, W;
    cin >> n >> W;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int j = 0; j < n; j++)
        cin >> b[j];
    // 每次计算前重置dp数组
    for(auto& row : dp){
        fill(row.begin(), row.end(), -1);
    }
    cout << knap(n, a, b, W) << endl;
    return 0;
}

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