arrays - 为什么我会看到这种奇怪的行为？

Question

该代码是0/1背包问题的递归动态规划。首先我要说的是，代码看起来是正确的，因为当我运行它时，它会显示结果，但前提是我取消注释 printf 行(请参阅突出显示的部分)，并且它与解决方案(我仅将其用于测试目的)，我觉得这很奇怪。有人可以告诉我为什么会发生这种情况吗？

int main() {    

    int DP_Recursive(int W, static int wt[], static int val[], int n, static int dp[][]);

    static int wt[5] = { 5, 10, 20, 30 };
    static int val[5] = { 50, 60, 100, 120 };

    static int dp[5][60]; //marker 2-D array

    for (int i = 0; i <= 5; i++) {
        for (int w = 0; w <= 50; w++) {
            dp[i][w] = -1;
        }
    }

    printf("The total loot is %d$.", DP_Recursive(50, wt, val, 2, dp));
}

//Recursive D.P. solution 
    
int DP_Recursive(int W, static int wt[], static int val[], int n, static int dp[5][60]) {
    //-------**HIGHLIGHTED PART**-----------
    printf("%d", dp[2][30]);
     //--------------------------
    //Base case
    if (n == 0 || W == 0)
        return 0;

    if (dp[n][W] != -1)
        return dp[n][W];

    if (wt[n-1] > W) {
        dp[n][W] = DP_Recursive(W, wt, val, n - 1, dp);
        return dp[n][W];
    } else {
        dp[n][W] = max(val[n-1] + DP_Recursive(W - wt[n-1], wt, val, n-1, dp),
                       DP_Recursive(W, wt, val, n-1, dp));
    }
    return dp[n][W];
}

Answer 1

代码中存在多个问题:

• [主要] DP_recursive 的原型(prototype)不正确:使用 int DP_Recursive(int W, int wt[], int val[], int n, static int dp[5][60])在 main() 之前的函数声明中函数(在 main 的主体之外)以及函数定义本身。

• [次要] main() 中的数组不需要声明static .

• [主要]初始化循环运行得太远:for (int i = 0; i <= 5; i++)使用 i 迭代 6 次范围从 0至5包括的。您应该使用<而不是<=在两个循环中。根据经验，在使用 <= 之前务必检查两次，并且总是更喜欢排除上限。

• [主要]内部初始化循环使用 50而不是60作为上限，导致数组部分初始化并导致结果不正确(未定义的行为)而不是 110 。最好使用 countof用于获取数组中元素数量的宏。

• [次要] 您应该以换行符结束输出 ( \n )

• [次要] main()应该返回0成功终止后。

• 您没有发布 max 的定义，建议将其定义为函数。

• 包含文件 <stdio.h>也不见了。

这是修改后的版本:

#include <stdio.h>

int DP_Recursive(int W, int wt[], int val[], int n, int dp[5][60]);

int max(int a, int b) {
    return a < b ? b : a;
}

#define countof(a)  (sizeof(a) / sizeof((a)[0]))  // number of elements in an array

int main() {    
    int wt[5] = { 5, 10, 20, 30 };
    int val[5] = { 50, 60, 100, 120 };
    int dp[5][60]; //marker 2-D array

    for (size_t i = 0; i < countof(dp); i++) {
        for (size_t w = 0; w < countof(dp[i]); w++) {
            dp[i][w] = -1;
        }
    }
    printf("The total loot is %d$.\n", DP_Recursive(50, wt, val, 2, dp));
    return 0;
}

//Recursive D.P. solution 
    
int DP_Recursive(int W, int wt[], int val[], int n, int dp[5][60]) {
    //-------**HIGHLIGHTED PART**-----------
    printf("%d ", dp[2][30]);
    //--------------------------

    //Base case
    if (n == 0 || W == 0)
        return 0;

    if (dp[n][W] != -1)
        return dp[n][W];

    if (wt[n-1] > W) {
        dp[n][W] = DP_Recursive(W, wt, val, n - 1, dp);
        return dp[n][W];
    } else {
        dp[n][W] = max(val[n-1] + DP_Recursive(W - wt[n-1], wt, val, n-1, dp),
                       DP_Recursive(W, wt, val, n-1, dp));
    }
    return dp[n][W];
}