Tushar's Birthday | Unbounded Knapsack | Dynamic Problem | C++ solution

 

Problem Description:

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).

NOTE:

• 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.

Input Format:

Friends : List of integers denoting eating capacity of friends separated by space.
Capacity: List of integers denoting filling capacity of each type of dish.
Cost : List of integers denoting cost of each type of dish.

Constraints:

• 1 <= Capacity of friend <= 1000
• 1 <= No. of friends <= 1000
• 1 <= No. of dishes <= 1000

Example:

Input:

    2 4 6

    2 1 3

    2 5 3

Output:

    14

Explanation: 

First friend will take 1st and 2nd dish, second friend will take 2nd dish twice.  Thus, total cost = (5+3)+(3*2)= 14

Approach:

Its an unbounded knapsack problem as we can use 1 or more instances of any resource. A simple 1D array, say dp[W+1] can be used such that dp[i] stores the maximum value which can achieved using all items and i capacity of knapsack. Note that we use 1D array here which is different from classical knapsack where we used 2D array. Here number of items never changes. We always have all items available.

We can recursively compute dp[] using below formula

dp[i][0] = 0  for i ->0 to B.size()

dp[0][j] = INT_MAX/2  for j ->1 to Max capacity of Friend  

dp[i][j] = min of these 3 conditions:

a. if eaten and don't repeat dp[i-1][j-B[i-1]]+C[i-1]

b. don't eat and leave dp[i-1][j]

c. eat and repeat that dish dp[i][j-B[i-1]] +C[i-1]

We perform Unbounded knapsack on a friend with the highest Capacity which will build our DP matrix. Then simply sum for all Capacities given:

Sol += dp[B.size()][A[i]]

Problem Solution in C++ Programming Language:

code:

int Solution::solve(const vector<int> &A, const vector<int> &B, 

                                          const vector<int> &C) 
{
    int k=*(max_element(A.begin(),A.end()));
    int m=B.size();
    int dp[m+1][k+1];
    for(int i=0;i<=m;i++)
        dp[i][0]=0;
    for(int j=1;j<=k;j++)
        dp[0][j]=INT_MAX/2;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(B[i-1]>j) dp[i][j]=dp[i-1][j];
            else
                dp[i][j]= min(C[i-1]+dp[i-1][j-B[i-1]],

                    min(C[i-1]+dp[i][j-B[i-1]],dp[i-1][j]));
        }
    }
    int sol=0;
    for(int i=0;i<A.size();i++)
    {
        sol+=dp[m][A[i]];
    }
    return sol;
}

Please share your reviews.

thanks for reading.👍😊

If you like the solution please share with your friends.

and for more dynamic programming question for interview preparation