Minimum Cost To Buy Oranges

Write a recursive function minCostToBuyOrangesHelper(idx, requiredWeight, n) to return the Minimum cost to buy exactly requiredWeight Kg oranges with (idx+1) Kg to N kg packets.

1. Our minimum cost for weight W will be : minCostToBuyOrangesHelper(idx, W, n)
2. Now at any instant (idx, requiredWeight, n), we have two options:
   1. The option of taking this packet:

cost[idx] + minCostToBuyOrangesHelper(idx, requiredWeight - (idx + 1), n, cost)

        2. The option of skipping this packet and moving to the next packet:

minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)

3. We will take the minimum of these two options as the minimum cost for instant minCostToBuyOrangesHelper(idx, requiredWeight, n)

4. Base cases are:

1. When requiredWeight is 0 then return 0.
2. if we reached the end and idx = n and requiredWeight != 0 then return maximum value (INT_MAX) as now it’s impossible to buy the requiredWeight.
3. If requiredWeight != 0 and requiredWeight  < (idx+1) then return maximum value (INT_MAX) as it’s impossible to buy requiredWeight  from greater weight packets.
   4. Also, take care of packets which are not available. The minimum cost for those idx  will have only one option:
   1. The option of skipping this packet and moving to the next packet:

minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)

We will write a recursive function minCostToBuyOrangesHelper(idx, requiredWeight, n) to return the Minimum cost to buy exactly requiredWeight Kg oranges with (idx+1) Kg to N kg packets. Then we will use a Dynamic Programming approach to memoize the calls in a DP matrix minCost[idx][requiredWeight] which will save the results of calls and will return the result when we again try to call for the same values.

Our minimum cost for weight W will be : minCostToBuyOrangesHelper(idx, W, n)

1. Now at any instant (idx, requiredWeight, n), we have two options:
   1. The option of taking this packet:

cost[idx] + minCostToBuyOrangesHelper(idx, requiredWeight - (idx + 1), n, cost)

1. The option of skipping this packet and moving to the next packet:

minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)

1. We will take the minimum of these two options as the minimum cost for instant minCostToBuyOrangesHelper(idx, requiredWeight, n) and will save this in our DP matrix minCost[idx][requiredWeight] (initially filled with -1s).
2. Base cases are:
   1. If answer is already present in minCost[idx][requiredWeight] then return the same value.
   2. When requiredWeight is 0 then return 0.
   3. If we reached the end and idx = n and requiredWeight != 0 then return maximum value (INT_MAX) as now it’s impossible to buy the requiredWeight.
   4. If requiredWeight != 0 and requiredWeight  < (idx+1) then return maximum value (INT_MAX) as it’s impossible to buy requiredWeight  from greater weight packets.
3. If dp[idx][requiredWeight] is not equal to -1, then we will return it.
4. Also, take care of packets that are not available. The minimum cost for those idx  will have only one option:
   1. The option of skipping this packet and moving to the next packet:

minCostToBuyOrangesHelper(idx + 1, requiredWeight, n, cost)

    5. Before returning the answer, store it in the dp array.

We will write an iterative DP where minCost[i][j] denotes the minimum cost of buying exactly 'j' kg Oranges with 1 to 'i’ kg packets of oranges.

1. The base cases are:
2. We will be Initializing 0th row with INF (Max Value) as we can’t buy any oranges with a packet having weight ‘0’ kg.
   1. We Initializing 0th column with 0 as cost of filling 0kg at any point in 0.
3. Now iterating over ‘i’ for different weights of packets (from i = 0 to i = n) we will iterate for buying exactly ‘j’ kg Oranges (from j = 0 to j = w). So transition relations are:
   1. If 'i' kg packet of orange is unavailable then, for all values of j :

minCost[i][j] = minCost[i - 1][j]

1. If  i > j means capacity of the bag is less then weight of item then:

 minCost[i][j] = minCost[i - 1][j];

    2. If i <= j get minimum cost either by including it or excluding it:

minCost[i][j] = min(minCost[i - 1][j], minCost[i][j - i] + cost[i - 1]);

    3. So finally we have our minimum cost in minCost[n][w]. If it’s equal to INF (Max Value), then return -1 else return the result.

We will write an iterative DP using 1D DP array where minCost[i] denotes Minimum cost of buying exactly 'i' kg Oranges with all the packets of oranges.

1. The base cases are:
   1. Initializing minCost[0]  = 0 for buying exactly 0 kg oranges.
   2. Initializing all other values in minCost[] with the  INF (Max Value).
2. Now iterating over ‘j’ for buying exactly ‘j’ kg Oranges (from j = 0 to j = w), we will iterate for different weights of packets ‘i’ (from i = 0 to i = n). So transition relations are:
   1. If 'i' kg packet of orange is unavailable then, for all values of j :

continue without changing minCost as they can’t contribute to minimizing cost.

1. If  i > j means capacity of the bag is less then weight of item then:

continue without changing minCost as they can’t contribute to minimizing cost.

    2. If i <= j get minimum cost either by including it or excluding it:

minCost[i] = min(minCost[i], minCost[i - j] + cost[j - 1]);

    3. So finally we have our minimum cost in minCost[w]. If it’s equal to INF (Max Value), then return -1 else return the result.