The problem in the code seems to be :-
if(maxMoney < cost[index])
return 0;
here you are returning that no items after current item cannot fit in the knapsack but there might be a item that has cost smaller than maxMoney
.
Remove the above statement and do following modification :-
int findOutput(int maxMoney,int index,int numOfItems,int *cost,int *weight, int **output){
if(index >= numOfItems)
return 0;
if(output[maxMoney][index] != -1)
return output[maxMoney][index];
int a = 0;
if(maxMoney >= cost[index]) {
a = findOutput( maxMoney-cost[index],index+1,numOfItems,cost,weight,output) + weight[index]; }
int b = findOutput(maxMoney,index+1,numOfItems,cost,weight,output);
output[maxMoney][index] = max(a,b);
return output[maxMoney][index];
}
Check only while calculating a if maxMoney is greater than or equal to cost of item so that there is a chance to include the item else that case will have zero value.
Note :- Dont use zero as sentinel values for memoization try negative (-1) because there can be cost of zero but negetive is impossible.