When I put the example weights and profits in recursive and top-down solution and run, the max_profit returned is 3 and not 10 as mentioned in the Introduction.
Not able to understand why? Please help
Hi @Darshini_Parikh
You are trying to compare the results of two totally different problems
- The output 10 is for the problem of Merry’s example, who wants to carry some fruits in the knapsack to get maximum profit.
- The output 3 is for the problem of given a set of positive numbers, finding the total number of subsets whose sum is equal to a given number ‘S’.
If you want to modify your Merry’s example and get maximum profit by the top-down approach you need to modify the complete code, you would not get desired results by simply entering the weights and profit in the code of a totally different problem.
Hope it will help, Happy Learning 
1 Like
Hi @Shahrukh_Naeem ,
I am still not able to follow, the problem statement clearly states “Write a function that returns the maximum profit”. In the visual representation of algorithm example, also we chose 22 as that was the max profit from all acceptable combinations having total weight less than or equal to the capacity.
So based on these the solutions given for the first part of the problem should also return output 10, right?
How is the reference to the total number of subsets relevant here?
Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: 0/1 Knapsack - Grokking Dynamic Programming Patterns for Coding Interviews
Yes, you are right, the output should be 10.
Consider making the following changes in your main () function then you would find the desired output:
int main(int argc, char *argv[])
{
Knapsack ks;
vector<int> profits = {4, 5, 3, 7};
vector<int> weights = {2, 3, 1, 4};
int maxProfit = ks.solveKnapsack(profits, weights, 5);
cout << "Total knapsack profit ---> " << maxProfit << endl;
}
For reference, I have attached the screenshot with desired output (10).
Hope this will help you, Happy Learning
1 Like