Minimum Cost to Buy Rice

One will get a clear intuition that a simple greedy approach will not work. A naive recursive approach that can later be extended to implement a DP solution is discussed here.

Let (i, j) recursive call return the minimum cost to buy exactly ‘j’ kgs of rice only from the first ‘i’ shops, then to calculate (i, j): we can avoid buying anything from the i’th shop, in this case, we will make a transition from (i-1, j) -> (i, j). If in case we plan to buy rice bags from the i’th shop then there can be two conditions, the first one is the case where we are buying from the i’th shop for the first time, in this case, we will make a transition of (i-1, j-i) -> (i, j). Another case here can be, when we have already bought a bag from the i’th shop and plan to buy more bags from the i’th shop now, in this case, in this case, we will make a transition from (i, j-i) -> (i, j). Remember that the answer for (i, j) will be the minimum value amongst the three transitions discussed above.

Our final answer will be the minimum of all the recursive calls (i, W) for 1 ≤ i ≤ N.

The steps are as follows :

1. Initialize a variable ‘Price’ to INT_MAX, this variable will store the final answer.
2. Make initial recursive calls (i, W) for all 1 ≤ i ≤ N, update the value of ‘Price’ so that it stores the minimum value returned by these recursive calls.
3. In the recursive function:
   • End the recursion using base condition when either ‘i’ or ‘j’ equals 0.
   • Initialize a variable ‘curAns’ to store the answer for the (i, j) recursive call.
   • Do the first transition from (i-1, j) to (i, j).
   • If the Cost[i-1] is not equal to -1, then do the other two transitions: (i-1, j-i) to (i, j) and (i, j-i) to (i, j).
   • Update ‘curAns’ to store the minimum value of all these three transitions, and finally return this value to end the current recursive call.
4. Finally, check if ‘Price’ is still equal to INT_MAX, this means that it is not possible to buy the rice and we will return -1 in this case. Else return the value stored in ‘Price’.

One will get a clear intuition that a simple greedy approach will not work. This is a problem that can easily be solved using dynamic programming. Dynamic programming involves figuring out the states of the DP and building a transition logic to calculate the state. It is highly suggested to have a basic idea about dynamic programming before solving this problem.

Let DP[i][j] store the minimum cost to buy exactly ‘j’ kgs of rice only from the first ‘i’ shops. Suppose we have already calculated the answer for all the DP-matrix values till ‘i-1’. Now we have to move further and include the contribution of the i’th shop, then to calculate DP[i][j] for all ‘j’ values belonging to [0, W] we need to build some transition logic.

We have many choices, let's explore each one of them. We can avoid buying anything from the i’th shop, in this case, the value DP[i][j] will be equal to DP[i-1][j], this is because we will make a transition from (i-1, j) -> (i, j). If in case we plan to buy rice bags from the i’th shop then there can be two conditions, the first one is the case where we are buying from the i’th shop for the first time, in this case, DP[i][j] = DP[i-1][j-i] + COST[i], this is because we will make a transition from (i-1, j-i) -> (i, j). Another case here can be, when we have already bought a bag from the i’th shop and plan to buy more bags from the i’th shop now, in this case, DP[i][j] = DP[i][j-i] + COST[i], this is because we will make a transition from (i, j-i) -> (i, j). Remember that we will store the minimum of the above three transitions finally in DP[i][j].

We can finally return the minimum of DP[i][W] where 1 ≤ i ≤ N.

To implement the above logic recursively, initialize all the values in the DP matrix equal to a very large number, as we will be using the operation to find the minimum of the three transitions discussed above, a very large initial value will avoid the altering of the answer because of the initialized value, though we will initialize the first row (corresponding to i=0) with a value equal to 0, this will be used as a base condition to end the recursive calls. Now make recursive calls to find the answer when the total weight is equal to ‘W’, ie: make initial calls to calculate DP[i][W] for all 1 ≤ i ≤ N, and return the minimum of these recursive calls. Inside the recursive function, calculate the current state from the three transitions discussed above. Also, remember to memoize the solution to avoid recomputation.

The steps are as follows :

1. Declare a ‘DP’ matrix of size (N + 1) * (W + 1). Initialize all the cells to INT_MAX, except the first column. Initialize all the cells in the first column (corresponding to a weight equal to 0) to value 0.
2. Initialize a variable ‘Price’ to INT_MAX, this variable will store the final answer.
3. Make initial recursive calls (i, W) for all 1 ≤ i ≤ N, update the value of ‘Price’ so that it stores the minimum value returned by these recursive calls.
4. In the recursive function:
   • End the recursion using base condition when either ‘i’ or ‘j’ equals 0.
   • If the value of DP[i][j] is not equal to INT_MAX, then return the recursive call as we have already calculated the value for this and stored that in DP[i][j].
   • Initialize a variable ‘curAns’ to store the answer for the (i, j) recursive call.
   • Do the first transition from (i-1, j) to (i, j).
   • If the Cost[i-1] is not equal to -1, then do the other two transitions: (i-1, j-i) to (i, j) and (i, j-i) to (i, j).
   • Update ‘curAns’ to store the minimum value of all these three transitions, and finally, return this value to end the current recursive call. Also, store this value in DP[i][j] so that we don’t have to recalculate it in future.

Finally, check if ‘Price’ is still equal to INT_MAX, this means that it is not possible to buy the rice and we will return -1 in this case. Else return the value stored in ‘Price’.

One will get a clear intuition that a simple greedy approach will not work. This is a problem that can easily be solved using dynamic programming. Dynamic programming involves figuring out the states of the DP and building a transition logic to calculate the state. It is highly suggested to have a basic idea about dynamic programming before solving this problem.

Let DP[i][j] store the minimum cost to buy exactly ‘j’ kgs of rice only from the first ‘i’ shops. Suppose we have already calculated the answer for all the DP-matrix values till ‘i-1’. Now we have to move further and include the contribution of the i’th shop, then to calculate DP[i][j] for all ‘j’ values belonging to [0, W] we need to build some transition logic.

We have many choices, let's explore each one of them. We can avoid buying anything from the i’th shop, in this case, the value DP[i][j] will be equal to DP[i-1][j], this is because we will make a transition from (i-1, j) -> (i, j). If in case we plan to buy rice bags from the i’th shop then there can be two conditions, the first one is the case where we are buying from the i’th shop for the first time, in this case, DP[i][j] = DP[i-1][j-i] + COST[i], this is because we will make a transition from (i-1, j-i) -> (i, j). Another case here can be, when we have already bought a bag from the i’th shop and plan to buy more bags from the i’th shop now, in this case, DP[i][j] = DP[i][j-i] + COST[i], this is because we will make a transition from (i, j-i) -> (i, j). Remember that we will store the minimum of the above three transitions finally in DP[i][j].

We can finally return the minimum of DP[i][W] where 1 ≤ i ≤ N.

We can easily implement the above logic. Initialize all the values in the DP matrix equal to a very large number, as we will be using the operation to find the minimum of the three transitions discussed above, a very large initial value will avoid the altering of the answer because of the initialized value, though we will initialize the first row (corresponding to i=0) with a value equal to 0.

Now to calculate the cells of the DP matrix, run two ‘for’ loops, the first ‘for’ loop for the variable ‘i’ from 1 to N, and the second one for the variable ‘j’ from 0 to W. Finally, return the minimum of DP[i][W] where 1 ≤ i ≤ N.

Note that for the transition of the i’th state we are only using the i-1’th state, therefore we can reduce the space complexity by only storing the previous row (corresponding to the i-1’th row) to calculate the i’th row. This reduces the space needed from N*W to N as we no longer store all the values of the DP matrix. This is a standard method of reducing the space complexity of many questions that are solved using DP, though for the sake of simplicity we have not used this code in our editorial.

The steps are as follows :

1. Declare a ‘DP’ matrix of size (N + 1) * (W + 1). Initalize all the cells to INT_MAX, except the first column. Initialize all the cells in the first column (corresponding to weight equal to 0) to value 0.
2. Fill in the DP matrix, run an outer for loop for variable ‘i’ from 1 to N, and run an inner for loop for variable ‘j’ from 1 to W:
   • Consider the first transition from (i-1, j) to (i, j).
   • If the Cost[i-1] is not equal to -1, then consider the other two transitions: (i-1, j-i) to (i, j) and (i, j-i) to (i, j).
   • Update DP[i][j] to store the minimum value of all these three transitions.
3. Initialize a variable ‘Price’ to INT_MAX, this variable will store the final answer.
4. Run a for loop for variable ‘i’ from 1 to N, update the value of ‘Price’ to store the minimum value of DP[i][W].
5. Finally, check if ‘Price’ is still equal to INT_MAX, this means that it was not possible to buy the rice and we will return -1 in this case. Else return the value stored in ‘Price’.