The knapsack is not producing the expected results when using large numbers.

Question

Before I dive into the question, let me introduce myself. I am a Mobile Developer based in Warsaw who has dedicated the past two years to learning and preparing for interviews. Initially, I found even the simplest of problems difficult and would have to refer to editorials and discussion sections to understand them. However, in the last two years, I have successfully solved around 800 problems and participated in coding contests from time to time. Usually, I can solve three problems in a coding contest, though I have managed to successfully solve four problems on occasion. Now, back to the topic.

Here is the top-down approach of dynamic programming, knapSackRec is implemented recursively. But it's not working on the given test case:

W=5,
n=5,
wt{1,1,1,1,1},
v{1000000000,1000000000,1000000000,1000000000,1000000000,}

It is returning 2000000000 as output. But the correct output should be 5000000000.

My code is here:

#include <bits/stdc++.h>
using namespace std;
int static dp[102][1000005];

// Returns the value of maximum profit
int knapSackRec(int W, int wt[], int val[], int i)
{
    // Base condition
    if (i < 0)
        return 0;

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

    if (wt[i] > W) 
    {
        // Store the value of function call
        // stack in table before return

        return dp[i][W] = knapSackRec(W, wt, val, i - 1);
    }
    else 
    {
        // Store value in a table before return

        // Return value of table after storing
        return dp[i][W] = max(
                val[i] + knapSackRec(W - wt[i], wt, val, i - 1),
                knapSackRec(W, wt, val, i - 1)
        );
    }
}
    
int main()
{
    int val[] = { 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 };
    int wt[]  = { 1, 1, 1, 1, 1 };
    int W = 5;
    int n = sizeof(val) / sizeof(val[0]);
    memset(dp, -1, sizeof(dp));

    cout << knapSackRec(W, wt, val, n);
    return 0;
}

 

 

Answer 1

Will look into it by EOD