Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Guaranteed Job
0 like 0 dislike

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:


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);
        // 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;



in Interview-Experiences by Expert (500 points) | 351 views

1 Answer

0 like 0 dislike
Will look into it by EOD
by Expert (119,150 points)

Get best answers to any doubt/query/question related to programming , jobs, gate, internships and tech-companies. Feel free to ask a question and you will receive the best advice/suggestion related to anything you ask about software-engineering , development and programming problems .