We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shopping Offers

Number: 638

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given a list of item prices, a set of special bundle offers, and the exact quantities (needs) for each item, determine the minimum cost required to purchase exactly the desired items. You can use each special offer as many times as needed, but you cannot purchase more than the required quantity of any item.

Key Insights

  • Use recursive backtracking to explore combinations of special offers.
  • Apply memoization to cache solved subproblems and avoid redundant calculations.
  • At each step, evaluate whether buying items individually is cheaper than applying a special offer.
  • Only consider a special offer if it does not exceed the current needs.
  • The state can be represented as a tuple of current needs, which makes it a small state-space given the constraints (n ≤ 6 and needs[i] ≤ 10).

Space and Time Complexity

Time Complexity: Exponential in the worst case due to recursion, but practical performance is improved by memoization. The worst-case state space is O((needs[0]+1)(needs[1]+1)…(needs[n-1]+1)). Space Complexity: O((needs[0]+1)(needs[1]+1)…(needs[n-1]+1)) due to memoization storage.

Solution

We solve this problem using a recursive approach with memoization. Define a recursive function (dfs) that computes the minimum cost to satisfy a given need state:

  1. Base Case: Calculate the cost by purchasing remaining items at individual prices.
  2. For each available special offer, check if it is applicable (i.e., does not exceed the current needs). If applicable, subtract the offer quantities from the current needs to form a new state.
  3. Recursively calculate the minimum cost for the new state and update the answer accordingly.
  4. Use a memoization dictionary (or hashmap) keyed by the tuple/string representation of the needs to cache results and avoid duplicate calculations.

Code Solutions

def shoppingOffers(price, special, needs):
    # Dictionary for memoization: key -> tuple(needs), value -> minimal cost
    memo = {}
    
    def dfs(current_needs):
        # Use tuple as key for immutable state representation
        needs_tuple = tuple(current_needs)
        if needs_tuple in memo:
            return memo[needs_tuple]
        
        # Compute cost without any special offers (individual item purchase)
        cost = sum(current_needs[i] * price[i] for i in range(len(price)))
        
        # Try each special offer
        for offer in special:
            new_needs = []
            # Check if offer can be applied to current needs
            for i in range(len(price)):
                if offer[i] > current_needs[i]:
                    break  # Cannot use this offer as it exceeds the need for item i
                new_needs.append(current_needs[i] - offer[i])
            else:
                # Offer is applicable, choose the minimum between current cost and cost with the offer
                cost = min(cost, offer[-1] + dfs(new_needs))
        
        memo[needs_tuple] = cost
        return cost
    
    return dfs(needs)

# Example usage:
print(shoppingOffers([2,5], [[3,0,5],[1,2,10]], [3,2]))  # Expected Output: 14
← Back to All Questions