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;
}