How can i solve it?

#1

please give me some hint ?

#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

during filling the matrix i need to check val[i-1]!=-1???