Minimum money needed

#1

i am just trying recursive approach , but getting wrong answer.
can u please check my code , where i am doing mistake

#2

Don’t try to increase the value of address of weight and value arrays. Also try to memoize your state otherwise you’ll get a tle.

#3

yes i will memoize the state , but what is the actual problem in incrementing the pointer
becoz in almost every problem of recursion involving arrays , i have solved that by incrementing the pointer .

even i have solved 0 1 knapsack by this way
you can check it https://ide.codingblocks.com/s/284420

but when i am taking min value , it’s creating the problem , and answer is giving 0 , due to the answer returned from the base case .

so i think problem is here due to base case.
so what should be correct answer from the base case?

#4

i am now just interested to know the run it by recursively .
latter i will memoize the solution

#5

Yes you have to increase the position but don’t increase it that way. Use a variable and then access it .

#6

i didn’t get the point , that ‘take the variable and use it’.
can you please tell me with example or mark in my code by comments

#7

ll A[300005];
ll cal( ll index , ll n, ll wt) {
if ( wt == 0) {
return 0;
}
if (index > n) {
return 10000000;
}
ll a = 100000000;
if (A[index] != -1)
a = cal(index + 1, n, wt - index) + A[index];
ll b = cal(index + 1, n, wt);
return min(a, b);
}

#8

still not working

although i have solved it iteratively , but recursive creating problem

#9

https://ide.codingblocks.com/s/284956 Have a look at this for reference. I have also coded it recursively.

#10

If your doubt has been resolved please close this doubt.