Approach #1 Using Recursion [Accepted]
Before discussing the steps involved in the process, we need to note a few points. Firstly, whenever an offer is used from amongst the ones available in the list, we need to update the appropriately, such that the number of items in the current offer of each type are deducted from the ones in the corresponding entry in .
Further, an offer can be used only if the number of items, of each type, required for using the offer, is lesser than or equal to the ones available in the current .
Now, let's discuss the algorithm. We make use of a
shopping(price,special,needs) function, which takes the and list along with the current(updated) as the input and returns the minimum cost of buying these items as required by this list.
In every call of the function
shopping(price,special,needs), we do as follows:
Determine the cost of buying items as per the array, without applying any offer. Store the result in .
Iterate over every offer in the list. For every offer chosen, repeat steps 3 to 5.
Create a copy of the current in a list(so that the original needs can be used again, while selecting the next offer).
Try to apply the current offer. If possible, update the required number of items in .
If the current offer could be applied, find the minimum cost out of and +
shopping(price,special,clone). Here, refers to the price that needs to be paid for the current offer. Update the with the minimum value.
Return the corresponding to the minimum cost.
We need to note that the needs to be updated afresh from (coming to the current function call) when we choose a new offer. This needs to be done, because solely applying the next offer could result in a lesser cost than the one resulting by using the previous offer first.
Approach #2 Using Recursion with memoization [Accepted]
In the last approach, we can observe that the same can be reached by applying the offers in various orders. e.g. We can choose the first offer followed by the second offer or vice-versa. But, both lead to the same requirement of updated and the cost as well. Thus, instead of repeating the whole process for the same state through various recursive paths, we can create an entry corresponding to the current set of in a HashMap, , which stores the minimum cost corresponding to this set of . Thus, whenever the same call is made again in the future through a different path, we need not repeat the whole process over, and we can directly return the result stored in the .
Analysis written by: @vinod23