Minimum money needed problem

#1

As said this problem is almost same as 0-n knapsack.
my code link for 0-n knapsack: https://ide.codingblocks.com/s/239769

what corrections i need to make in my code so that the problem is solved.
Please help.

#2

You cannot memoise the states as you dont know that you have got the best possible answer till now. Try without memoising. Like

int knapSack(int W, int wt[], int val[], int n)
{

if (n == 0 || W == 0) 
	return 0; 

if (wt[n - 1] > W) 
	return knapSack(W, wt, val, n - 1); 

else
	return max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));

}

#3

If we don’t memoise it then how can we use DP here.
I followed your approach and it gives correct ans for sample test case but gives WA on submitting.
code link: https://ide.codingblocks.com/s/240028
Please correct my code.

#4

@shubhamhalderO Let me check

#5

@amankumarkeshu if you have checked it please provide the solution.
i have been stuck in this problem for hours.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.