Minimum Cost To Buy Oranges

Posted: 21 Jul, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a bag of size 'W' kg and provided with the costs of packets with different weights of oranges as a list/array with the name 'cost'. Every i-th position in the cost denotes the price of 'i+1' kg packet of oranges.

If at any point in time the i-th cost is -1, it means that 'i+1' kg packet of orange is unavailable.

You are required to find the minimum total cost to buy exactly 'W' kg oranges and if it's not possible to buy precisely W kg oranges then print -1. There is an infinite supply of all available packet types.

Note :
Array index 'i' denotes the cost of (i+1)kg packet. 
Example: cost[0] is the cost of a 1kg packet of oranges.
Input Format :
The first line of each test case contains two single space-separated integers 'N' and 'W' where 'N' denotes the size of the array/list(cost), and 'W' is the bag's size.

The second line of each test case contains 'N' single space-separated integers denoting the values of the cost.
Output Format :
Print the minimum cost to buy exactly W kg oranges. If it's impossible, print "-1".
Note :
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints :
1 <= N <= 1000
1 <= W <= 1000
-1 <= cost[i] <= 1000000

Time Limit: 1sec
Approach 1

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)
Try Problem