# Minimum Cost To Buy Oranges

#### 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
```

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.

- Our minimum cost for weight W will be : minCostToBuyOrangesHelper(idx, W, n)
- Now at any instant (idx, requiredWeight, n), we have two options:
- 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:

- When requiredWeight is 0 then return 0.
- 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.
- 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:- 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)`

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

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

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

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

- 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).
- Base cases are:
- If answer is already present in minCost[idx][requiredWeight] then return the same value.
- When requiredWeight is 0 then return 0.
- 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.
- If requiredWeight != 0 and requiredWeight < (idx+1) then return maximum value (INT_MAX) as it’s impossible to buy requiredWeight from greater weight packets.

- If dp[idx][requiredWeight] is not equal to -1, then we will return it.
- Also, take care of packets that are not available. The minimum cost for those idx will have only one option:
- 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.

- The base cases are:
- We will be Initializing 0th row with INF (Max Value) as we can’t buy any oranges with a packet having weight ‘0’ kg.
- We Initializing 0th column with 0 as cost of filling 0kg at any point in 0.

- 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:
- If 'i' kg packet of orange is unavailable then, for all values of j :

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

- 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.

- The base cases are:
- Initializing minCost[0] = 0 for buying exactly 0 kg oranges.
- Initializing all other values in minCost[] with the INF (Max Value).

- 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:
- 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.

- 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.