Why am I seeing this bizarre behaviour?

user_13923657 0
Viewed 67

The code is recursive dynamic programming for the 0/1 Knapsack problem. So let me start by saying that the code seems correct because when I run it, It shows results but only if I uncomment the printf line (please see the highlighted part) and it has nothing to do with the solution (I used it only for testing purpose) which I find totally weird. Can somebody please tell me why is this happening.

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];
}
knapsack-problem dynamic c arrays
1 Answers

There are multiple issues int the code:

  • [Major] The prototype for DP_recursive is incorrect: use int DP_Recursive(int W, int wt[], int val[], int n, static int dp[5][60]) in both the function declaration before the main() function (outside the body of main) and for the function definition itself.

  • [Minor] the arrays in main() do not need to be declared static.

  • [Major] the initialization loops run one step too far: for (int i = 0; i <= 5; i++) iterates 6 times with i ranging from 0 to 5 inclusive. You should use < instead of <= in both loops. As a rule of thumb, always check twice before using <=, and always prefer excluded upper bounds.

  • [Major] the inner initialization loop uses 50 instead of 60 as the upper bound, causing the array to be partially initialized and result incorrect (undefined behavior) instead of 110. It is better to use a countof macro to get the number of elements in an array.

  • [Minor] you should end the output with a newline (\n)

  • [Minor] main() should return 0 upon successful termination.

  • you did not post the definition of max, it is advisable to define it as a function.

  • the include file <stdio.h> is missing too.

Here is a modified version:

#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];
}
user_45932670
Related