Minimum Money Needed

#1

How to solve this problem

#2

This problem is can be reduced to 0-1 Knapsack Problem. So in cost array, we first ignore those packets which are not available i.e; cost is -1 and then traverse the cost array and create two array val[] for storing cost of ‘i’ kg packet of orange and wt[] for storing weight of corresponding packet. Suppose cost[i] = 50 so weight of packet will be i and cost will be 50.
Algorithm :

Create matrix min_cost[n+1][W+1], where n is number of distinct weighted packets of orange and W is maximum capacity of bag.
Initialize 0th row with INF (infinity) and 0th Column with 0.
Now fill the matrix
    if wt[i-1] > j then min cost[i][j] = min cost[i-1][j] ;
    if wt[i-1] <= j then min cost[i][j] = min(min cost[i-1][j], val[i-1] + min_cost[i][j-wt[i-1]]);
If min cost[n][W]==INF then output will be -1 because this means that we cant not make make weight W by using these weights else output will be min cost[n][W].
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.