Leetcode 638. Shopping Offers
Problem explanation
In a store, items are available to purchase and each item has a defined price. However, there are some special offers available which consist of one or more different kinds of items available at a sale price.
Our task is to purchase a certain number of items at the lowest possible price by optimally utilizing the special offers. Each special offer is presented in the form of an array where the last element is the price to pay for this offer and the other elements represent the quantity of each item in this offer.
We can use any of the special offers infinitely many times but we are not allowed to buy more items than we want, even if that would decrease the total price.
For example, if the item's prices are [2,5], special offers are [[3,0,5],[1,2,10]], and the number of items we need to buy is [3,2].
The special offers mean:
- We can pay $5 for 3 of the first item.
- We can pay $10 for 1 of the first item and 2 of the second item.
The optimal way to buy the items we need is to pay 4 for the remaining 2 first items. Hence, the minimum amount we have to pay is $14.
Approach
The solution uses a Depth First Search (DFS) with backtracking where at each depth of the recursion, it tries to apply each special offer.
It starts by calculating the total price if we buy each item at its original price without considering any special offer. Then it will iterate over each special offer to check if the offer is valid meaning that we won't buy more items than we need by using this offer. If the offer is valid, we subtract the quantities in the offer from our needs and calculate the minimum price using this offer and recursively apply the other offers.
After exploring all the possibilities using a particular offer, we backtrack and add the quantities in the offer back to our needs and try the next offer.
Finally, we return the minimum price after exploring all the possibilities.
Example
Let's simulate the process using the first example from the problem:
Need: [3, 2] Price: [2, 5] Special offers: [[3,0,5],[1,2,10]]
- Initially, we calculate the total price if we buy each item at its original price without considering any special offer. The price will be 23 + 52 = 6 + 10 = 16.
- We try the first offer [3,0,5] which means we can get 3 of the first item for $5. After applying this offer, our need becomes [0,2] and the price we pay is 5. Then we recursively check the other offers.
- The second offer [1,2,10] is not valid for the current need because it offers 1 of the first item which we don't need. So, we continue to the next offer.
- As we have checked all the offers and there are still items in our need [0,2], we buy each remaining item at its original price which will cost us 5*2=10. So the total cost using the first offer will be 5 (for the first offer) + 10 (for the remaining items) = 15.
- We backtrack and try the second offer [1,2,10]. After applying this offer, our need becomes [2,0] and the price we pay is 10. Then we recursively check the other offers.
- As the first offer [3,0,5] provides more of the first item than we need, we skip it.
- After checking all the offers and there are still items in our need [2,0], we buy each remaining item at its original price which will cost us 2*2=4. So the total cost using the second offer will be 10 (for the second offer) + 4 (for the remaining items) = 14.
- As there are no more offers to check, we return the minimum price which is min(16, 15, 14) = 14.
The following sections contain the Python, Java, JavaScript, C++, and C# solutions for this problem. Please understand that none of these solutions are code-golf solutions. They are written to be as clear and understandable as possible so you can actually learn from them. Comments are included to further aid in the explanation of the solution.
Python Solution
1 2python 3class Solution: 4 def shoppingOffers(self, price, special, needs): 5 def dfs(s): 6 # Calculate the initial total price for current needs without considering any special offer 7 val = sum(needs[i]*price[i] for i in range(n)) 8 # Iterate over each offer starting from s 9 for i in range(s, m): 10 offer = special[i] 11 # Check if the offer is valid for current needs 12 if all(needs[j] >= offer[j] for j in range(n)): 13 # Subtract the offer quantities from needs 14 for j in range(n): 15 needs[j] -= offer[j] 16 # Update the total price including the current offer price and recursively check other offers 17 val = min(val, offer[-1] + dfs(i)) 18 # Backtrack and add the offer quantities back to needs 19 for j in range(n): 20 needs[j] += offer[j] 21 return val 22 23 n, m = len(price), len(special) 24 return dfs(0)
Java Solution
1
2java
3public class Solution {
4 public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
5 return dfs(price, special, needs, 0);
6 }
7
8 // Helper function to perform DFS with backtracking
9 private int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int s) {
10 int n = price.size();
11 int val = 0;
12 // Calculate the initial total price for current needs without considering any special offer
13 for (int i=0; i<n; i++)
14 val += price.get(i) * needs.get(i);
15 // Iterate over each offer starting from s
16 for (int i=s; i<special.size(); i++) {
17 List<Integer> offer = special.get(i);
18 boolean valid = true;
19 // Subtract the offer quantities from needs and check if the offer is valid
20 for (int j=0; j<n; j++) {
21 int temp = needs.get(j) - offer.get(j);
22 if (valid && temp < 0) valid = false;
23 needs.set(j, temp);
24 }
25 // If the offer is valid, update the total price including the current offer price and recursively check other offers
26 if (valid) val = Math.min(val, offer.get(n) + dfs(price, special, needs, i));
27 // Backtrack and add the offer quantities back to needs
28 for (int j=0; j<n; j++)
29 needs.set(j, needs.get(j) + offer.get(j));
30 }
31 return val;
32 }
33}
JavaScript Solution
1 2javascript 3var shoppingOffers = function(price, special, needs) { 4 return dfs(price, special, needs, 0); 5}; 6 7var dfs = function(price, special, needs, s) { 8 var n = price.length; 9 var val = 0; 10 // Calculate the initial total price for current needs without considering any special offer 11 for (var i=0; i<n; i++) 12 val += price[i] * needs[i]; 13 // Iterate over each offer starting from s 14 for (var i=s; i<special.length; i++) { 15 var offer = special[i]; 16 var valid = true; 17 // Subtract the offer quantities from needs and check if the offer is valid 18 for (var j=0; j<n; j++) { 19 var temp = needs[j] - offer[j]; 20 if (valid && temp < 0) valid = false; 21 needs[j] = temp; 22 } 23 // If the offer is valid, update the total price including the current offer price and recursively check other offers 24 if (valid) val = Math.min(val, offer[n] + dfs(price, special, needs, i)); 25 // Backtrack and add the offer quantities back to needs 26 for (var j=0; j<n; j++) 27 needs[j] += offer[j]; 28 } 29 return val; 30};
C++ Solution
1
2c++
3class Solution {
4public:
5 int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
6 return dfs(price, special, needs, 0);
7 }
8
9private:
10 int dfs(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int s) {
11 int n = price.size();
12 int val = 0;
13 // Calculate the initial total price for current needs without considering any special offer
14 for (int i=0; i<n; i++)
15 val += price[i] * needs[i];
16 // Iterate over each offer starting from s
17 for (int i=s; i<special.size(); i++) {
18 vector<int> offer = special[i];
19 bool valid = true;
20 // Subtract the offer quantities from needs and check if the offer is valid
21 for (int j=0; j<n; j++) {
22 int temp = needs[j] - offer[j];
23 if (valid && temp < 0) valid = false;
24 needs[j] = temp;
25 }
26 // If the offer is valid, update the total price including the current offer price and recursively check other offers
27 if (valid) val = min(val, offer[n] + dfs(price, special, needs, i));
28 // Backtrack and add the offer quantities back to needs
29 for (int j=0; j<n; j++)
30 needs[j] += offer[j];
31 }
32 return val;
33 }
34};
C# Solution
1
2csharp
3public class Solution {
4 public int ShoppingOffers(IList<int> price, IList<IList<int>> special, IList<int> needs) {
5 return dfs(price, special, needs, 0);
6 }
7
8 private int dfs(IList<int> price, IList<IList<int>> special, IList<int> needs, int s) {
9 int n = price.Count;
10 int val = 0;
11 // Calculate the initial total price for current needs without considering any special offer
12 for (int i=0; i<n; i++)
13 val += price[i] * needs[i];
14 // Iterate over each offer starting from s
15 for (int i=s; i<special.Count; i++) {
16 IList<int> offer = special[i];
17 bool valid = true;
18 // Subtract the offer quantities from needs and check if the offer is valid
19 for (int j=0; j<n; j++) {
20 int temp = needs[j] - offer[j];
21 if (valid && temp < 0) valid = false;
22 needs[j] = temp;
23 }
24 // If the offer is valid, update the total price including the current offer price and recursively check other offers
25 if (valid) val = Math.Min(val, offer[n] + dfs(price, special, needs, i));
26 // Backtrack and add the offer quantities back to needs
27 for (int j=0; j<n; j++)
28 needs[j] += offer[j];
29 }
30 return val;
31 }
32}
All programming solutions for this problem involve defining a depth-first search (DFS) method that's used to backtrack and find the minimal shopping price. Here's how we could do it for three languages i.e. Python, JavaScript, and Java:
Python solution has a nested function dfs() that runs the main algorithm. It starts by calculating the total price if we don't apply any special offers (multiply each item's price by its quantity and summing them all up). Then it iterates over each special offer and subtracts the quantity in the offer from our need list. After finding the total cost, it backtracks and returns the offer quantities back to our needs list.
JavaScript solution basically follows the same approach as the Python variant, but it uses separate functions to handle DFS and the main method. The JavaScript function shoppingOffers() starts by calling a dfs() function, which then performs a similar algorithm as the Python solution.
Java solution is just as similar to the Python and JavaScript solutions but has its own language specifics. The Java version uses a helper function to handle the DFS algorithm and does the subtracting and backtracking part in two separate for-loops. It also uses Java methods like List.get and List.set to work with lists.
Overall, all three solutions share a common approach but implement it slightly differently, based on the specific language constructs and standards. Python solution uses a nested function, JavaScript - separate functions, and Java - a helper function and separate for-loops. All the solutions first calculate the total price by multiplying each price with the corresponding index in the needs list and then use DFS and backtracking to explore each special offer and finally find the minimum price.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.