grid47 Exploring patterns and algorithms
Sep 4, 2024
9 min read
Solution to LeetCode 638: Shopping Offers Problem
In a store, there are n items available for sale, each with a given price. You are also given a list of special offers where you can buy multiple items at a discounted price. Your task is to determine the minimum total price to purchase the required quantities of each item, while utilizing the special offers optimally. You can use any offer as many times as you like, but cannot buy more items than you need.
Problem
Approach
Steps
Complexity
Input: You are given an array of prices, a list of special offers, and a list of the items you need to buy. Each offer consists of quantities of different items and the price for that offer.
• Explanation: You need 5 units of Item 0 and 6 units of Item 1. The best option is to buy the second offer twice and 1 more unit of Item 0 for a total cost of 26.
Approach: The optimal strategy involves recursively trying each special offer and calculating the total cost. Use memoization to store previously computed results to avoid redundant calculations.
Observations:
• We should take advantage of special offers that reduce the price for multiple items.
• We can recursively try each offer and compute the cost after applying the offer, then memoize the results to avoid recalculations.
Steps:
• Start by calculating the total cost without using any special offers.
• Then, for each special offer, reduce the 'needs' list accordingly and compute the resulting cost.
• Recursively try each offer and keep track of the minimum cost.
Empty Inputs:
• The problem will always have valid inputs, so there will never be an empty list for 'price', 'needs', or 'special'.
Large Inputs:
• The input sizes are manageable (n <= 6, special.length <= 100), so a solution with time complexity up to O(n^2) is feasible.
Special Values:
• Special cases include when all offers result in the same cost or when no offer provides any savings.
Constraints:
• The solution should handle up to 100 offers and 6 items efficiently.
map<vector<int>, int> mp;
intshoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
if(mp[needs]) return mp[needs];
int best = calculate(price, needs);
for(auto&sp: special) {
sub(needs, sp);
if(noneg(needs)) {
int woffer = sp.back() + shoppingOffers(price, special, needs);
best = min(best, woffer);
}
add(needs, sp);
}
return mp[needs] = best;
}
intcalculate(vector<int>&prices, vector<int>&needs) {
int res =0;
for(int i =0; i < needs.size(); i++) {
res += (needs[i] * prices[i]);
}
return res;
}
voidadd(vector<int>&needs, vector<int>&sp) {
for(int i =0; i < needs.size(); i++) {
needs[i] += sp[i];
}
}
voidsub(vector<int>&needs, vector<int>&sp) {
for(int i =0; i < needs.size(); i++) {
needs[i] -= sp[i];
}
}
boolnoneg(vector<int>&needs) {
for(int i =0; i < needs.size(); i++) {
if(needs[i] <0) returnfalse;
}
returntrue;
}
1 : Variable Initialization
map<vector<int>, int> mp;
This line initializes a map, 'mp', which stores the minimum cost for each combination of item quantities (represented as a vector). The key is a vector of integers representing the current needs, and the value is the minimum cost for fulfilling that set of needs.
This is the function signature of 'shoppingOffers'. It takes in the prices of items, the special offers, and the current needs (quantities of items to buy) as input. It returns the minimum cost to fulfill the needs considering the special offers.
3 : Memoization
if(mp[needs]) return mp[needs];
This line checks if the result for the current set of needs has already been computed. If so, it returns the cached result from the map 'mp' to avoid redundant calculations.
4 : Initial Calculation
int best = calculate(price, needs);
This line initializes the best cost as the result of the 'calculate' function, which computes the cost of fulfilling the needs without considering any special offers.
5 : Iterating over Offers
for(auto&sp: special) {
This loop iterates through each special offer in the 'special' vector. Each special offer contains a vector of item quantities and the price for that offer.
6 : Subtraction of Items
sub(needs, sp);
The 'sub' function subtracts the quantities of items in the special offer from the current 'needs' vector, simulating the purchase of the offer.
7 : Check for Valid Needs
if(noneg(needs)) {
This checks whether the remaining needs are all non-negative. If any need is negative, it means the current offer is invalid (i.e., the special offer cannot be used to fulfill the needs).
8 : Recursive Call with Special Offer
int woffer = sp.back() + shoppingOffers(price, special, needs);
This line recursively calculates the cost if the current special offer is used, adding the cost of the offer (sp.back()) to the result of fulfilling the updated needs.
9 : Update Best Cost
best = min(best, woffer);
This updates the 'best' variable to the minimum of the current 'best' and the new cost ('woffer') obtained from using the current special offer.
10 : Restore Needs
add(needs, sp);
The 'add' function restores the quantities of items in 'needs' by adding back the quantities subtracted by the special offer.
11 : Memoization Store
return mp[needs] = best;
This stores the computed 'best' result in the map 'mp' for the current set of needs, ensuring it can be reused in future calculations.
