-9
#include <bits/stdc++.h>
int func(int index,vector<int> &weight, vector<int> value, int n, int maxWeight,int sum,vector<vector<int>> &dp,int val)
{
    if(index==n)return val;
    if(dp[index][sum]!=-1)return dp[index][sum];

    int pick=INT_MIN,notpick=INT_MIN;
    if(sum+weight[index]<=maxWeight)
    pick=func(index+1,weight,value,n,maxWeight,sum+weight[index],dp,val+value[index]);
    notpick=func(index+1,weight,value,n,maxWeight,sum,dp,val);

    return dp[index][sum]=max(pick,notpick);
}
int knapsack(vector<int> weight, vector<int> value, int n, int maxWeight) 
{
    // Write your code here
    // in val=INT_MIN;
    
    vector<vector<int>>dp(n+1,vector<int>(maxWeight+1,-1));
    return func(0,weight,value,n,maxWeight,0,dp,0);
    
}

This is the standard knapsack problem implemented above. This code passed quite a few cases but it is failing in some and I can't seem to understand the issue with this approach. Someone please help try and keep the changes as minimal as possible as i want to know what is wrong with this approach

Dev Thakkar
  • 1
  • 7
    This question's code/phrasing suggests that it came from one of many countless coding challenge/puzzle scam sites. They take advantage of people who want to learn C++ by offering arcane coding puzzles and promising that you don't really need to study and learn C++ with a good textbook for many years, just do a bunch of meaningless coding puzzles. Everyone eventually realizes that they got scammed; these pointless coding puzzles are a waste of time, and there's nothing to be learned from them. But only after spending a lot of time doing them, with nothing to show for it. – Sam Varshavchik Sep 01 '23 at 15:20
  • 4
    [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Some programmer dude Sep 01 '23 at 15:21
  • 4
    If you want people to read your code, please make it readable. Proper formatting makes it easier to read and can even help you find the problem yourself. Not everyone knows what a "standard knapsack 0/1" problem is, add a description of the problem you are solving as well. "is failing for some testcases" - don't leave us guessing, find a representative one, hardcode it and make a [mre]. – teapot418 Sep 01 '23 at 15:31
  • 4
    when you need help with failing test cases you should show us those tests – 463035818_is_not_an_ai Sep 01 '23 at 15:33
  • 4
    You mean well, @teapot418, but after you've been on Stackoverflow for a few more years, and encounter this question, and its variations, a few hundred times you will conclude that these kinds of low-quality questions are unfixable and are, basically, write-only. – Sam Varshavchik Sep 01 '23 at 15:33
  • @SamVarshavchik I know this one is extremely unlikely to be salvaged, just trying to hint to OP how not to get their future questions nuked... – teapot418 Sep 01 '23 at 15:36
  • @SamVarshavchik think positive :). This question is unlikely to be salvaged, but one of OPs future questions might be an actual question. – 463035818_is_not_an_ai Sep 01 '23 at 15:43
  • 2
    Recommendation: Take the [tour] you elected to skip when you signed up at Stack Overflow. Also read [ask], at least the [asking questions](https://stackoverflow.com/help/asking) portion of the Help Center, and [Writing the Perfect question](https://codeblog.jonskeet.uk/2010/08/29/writing-the-perfect-question/). Asking a good question is hard work, but it's necessary to get a good answer. Plus if you have develop a good question-asking process, you're also developing a good question-answering process, and you'll find you don't have to post many questions. – user4581301 Sep 01 '23 at 17:27

0 Answers0