You are at the best toffee shop in the town. You see that there are different varieties of toffees in the shop.

Each type of toffee costs P rupees and contains C calories. You being a student have a fixed budget B rupees to spend on these toffees.

You want to maximize the total calories you gain by eating them.

Note : Any toffee can be eaten only once.

Your task is to write a program to output the maximum calories you gain with your budget (B rupees).

Bujhte parchina

I believe the dynamic programming style “DP Knapsack” algorithm would easily apply here, consider reading up on it on reference sources.

I could see it being used the following way - dp[i][j] would store the maximum calories that can be gained by considering the first ‘i’ toffees with a budget of ‘j’ rupees.

And after this processing, your answer will be dp[n][B]. (if n toffees are available)

Read it’s implementation and algorithm on a reference source like here - http://www.geeksforgeeks.org/knapsack-problem/

I hope I helped.