Question is misprinted

#1

I dont understand the use of N here, as we are given W weight, and array of size W itself, so i don’t know whats the use of N here.

#2

N is useless.its just there to confuse

#3

I still am getting wrong answers, could you help me out here?

#4

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].
#5

you can see this for reference