Approach on Solving this Problem?

Can you guys drop some hints on how can I approach this problem?

As it is Tushar’s Birthday on March 1st, he decided to throw a party to all his friends at TGI Fridays in Pune. Given are the eating capacity of each friend, filling capacity of each dish and cost of each dish. A friend is satisfied if the sum of the filling capacity of dishes he ate is equal to his capacity. Find the minimum cost such that all of Tushar’s friends are satisfied (reached their eating capacity).


Each dish is supposed to be eaten by only one person. Sharing is not allowed. Each friend can take any dish unlimited number of times. There always exists a dish with filling capacity 1 so that a solution always exists.


It seems to be a variation of the knapsack problem. Firstly, find what’s the maximum eating capacity of the friends. Say, it’s N. All other friends ranges b/w [1, N]

Now you have M denominations(M dishes)
each dish has two property, cost & capacity

so it now comes now to recursion.
you need to reach N
you have M elements

so either take ith element else don’t take. Choose minimum out of that two.

f(N,M)= Min( F(N-capacity[M])+cost[M], //you took Mth element
F(N,M-1) // you skipped Mth element

take care of base cases.

Convert it to DP. you are done with DP table

calculate for all friends now. since you calculated for N, other friends capacity already presented there as sub-problems.

Feel free to post your doubt if you have any issue implementing.

1 Like