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;

}