c++ - 使用部分初始化数组的内存问题(在 0/1 背包中)

Question

给定 n 个大小为 Ai、值(value)为 Vi 的元素，以及一个大小为 m 的背包。你背包里最多能放多少东西？

你在真实的面试中遇到过这个问题吗？是的例子给定 4 件尺寸为 [2, 3, 5, 7] 且值为 [1, 5, 2, 4] 的元素，以及一个尺寸为 10 的背包。最大值为 9。

备注您不能将项目分成小块，并且您选择的项目的总大小应小于或等于 m。

    int knapsack(int m, vector<int> A, vector<int> V) {
    int dp[m + 1], tmp[m + 1];


    for (int n = 1; n <= m; n++) { 
     //******the problem would disappear if i change n to start with 0

        dp[n] = (n < A[0]) ? 0 : V[0] ;
        tmp[n] = dp[n];
    }
    for (int i = 1; i < A.size(); i++) {
        for (int n = 1; n <= m; n++) {
            tmp[n] = dp[n];
        }
        for (int j = 1; j <= m; j++) {
            if (j >= A[i]) {
                dp[j] = max(tmp[j], (V[i] + tmp[j - A[i]]));
            }
        }
    }
    return dp[m];
}

我没有通过特定的测试用例，所有其他的都很好(甚至更大的 m 值)m = 10，A = [2,3,5,7]，V = [1,5,2,4]输出:563858905(实际上每次都是随机的)预期:9

我知道这个问题有些微不足道，但我真的很好奇这种情况下的内存分配过程

我猜想使用任何未在第一个内存位置初始化的数组都是危险的，有人可以向我确认吗？

Answer 1

我尝试了以下代码，这是您的一个更简单的版本；

#include <iostream>
using namespace std;

int knapsack(int m, int  A[], int V[], int size) {
    int dp[m+1], tmp[m+1];

    for (int n = 1; n <= m; n++) {  //*1*
        dp[n] = (n < A[0]) ? 0 : V[0] ;
        tmp[n] = dp[n];
    }
    for (int i = 1; i < 4; i++) { //*2*
        for (int n = 1; n <= m; n++) { //*3*
            tmp[n] = dp[n];
        }
        for (int j = 1; j <= m; j++) { //*4*
            if (j >= A[i]) {
                dp[j] = (tmp[j]> (V[i] + tmp[j - A[i]])? //*5*
                                tmp[j] :
                                (V[i] + tmp[j - A[i]])
                                );
            }
        }
    }
    cout << "answer:" << dp[m] << endl;
    return dp[m];
}
int main(){
        int a[]  = {2,3,5,7};
        int b[]  = {1,5,2,4};
        knapsack(10, a, b, 4);
        return 0;
}

并得到 8 作为答案，而不是随机数。

我不确定我的代码是否是你的正确版本，但幸运的是我注意到 V[i] + tmp[j-A[i]] 在标记为当 j=2 和 i=1 时，“\\*5”访问 tmp[0]，因为 A[1] == 2 和 2 >= A[1]。因此，在此逻辑中不初始化 tmp[0] 是不安全的。

所以，我想你是对的； tmp[0] 的未初始化值可能会改变结果值，(在某些情况下逻辑的流程也是如此，在 //*5 行的条件语句处>.)