Shopping Offers
Problem
Each item has a price; special offers bundle some items at a discount. Buy exactly the needed quantities at minimum cost.
price=[2,5] special=[[3,0,5],[1,2,10]] needs=[3,2]14def shopping_offers(price, special, needs):
from functools import lru_cache
@lru_cache(None)
def go(n):
cost = sum(p*q for p, q in zip(price, n))
for s in special:
if all(s[i] <= n[i] for i in range(len(n))):
cost = min(cost, s[-1] + go(tuple(n[i] - s[i] for i in range(len(n)))))
return cost
return go(tuple(needs))function shoppingOffers(price, special, needs) {
const memo = new Map();
function go(n) {
const k = n.join(',');
if (memo.has(k)) return memo.get(k);
let cost = n.reduce((s, q, i) => s + q * price[i], 0);
for (const s of special) {
if (s.slice(0, n.length).every((c, i) => c <= n[i]))
cost = Math.min(cost, s[s.length-1] + go(n.map((q, i) => q - s[i])));
}
memo.set(k, cost); return cost;
}
return go(needs);
}int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
return go(price, special, needs, new HashMap<>());
}
int go(List<Integer> price, List<List<Integer>> special, List<Integer> n, Map<String, Integer> memo) {
String k = n.toString(); if (memo.containsKey(k)) return memo.get(k);
int cost = 0; for (int i = 0; i < n.size(); i++) cost += n.get(i) * price.get(i);
for (List<Integer> s : special) {
boolean ok = true; List<Integer> r = new ArrayList<>(n);
for (int i = 0; i < n.size(); i++) { if (s.get(i) > n.get(i)) { ok = false; break; } r.set(i, n.get(i) - s.get(i)); }
if (ok) cost = Math.min(cost, s.get(s.size()-1) + go(price, special, r, memo));
}
memo.put(k, cost); return cost;
}map<vector<int>, int> memo;
int go(vector<int>& price, vector<vector<int>>& special, vector<int> n) {
if (memo.count(n)) return memo[n];
int cost = 0; for (int i = 0; i < (int)n.size(); i++) cost += n[i] * price[i];
for (auto& s : special) {
bool ok = true; vector<int> r = n;
for (int i = 0; i < (int)n.size(); i++) { if (s[i] > n[i]) { ok = false; break; } r[i] -= s[i]; }
if (ok) cost = min(cost, s.back() + go(price, special, r));
}
return memo[n] = cost;
}
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) { return go(price, special, needs); }Explanation
The goal is to buy exactly the quantities in needs as cheaply as possible, where you can either buy items one-by-one at full price or grab a special bundle that gives several items for a discount. The clever part is to describe the whole situation by just the list of remaining needs and solve smaller versions of the same problem.
The function go(n) answers "what is the cheapest way to buy exactly n?" First it computes a baseline cost: buy everything left at full price. Then it tries each offer that still fits (no offer may give you more of an item than you still need), subtracts those items, and recurses on the smaller need with go(...).
It works because every shopping plan is just a sequence of offers plus some full-price buys, and trying every applicable offer at each step explores all of them. Memoization (lru_cache) stores the answer for each remaining-needs tuple so the same state is never recomputed.
Example: price=[2,5], needs=[3,2]. Baseline is 3·2 + 2·5 = 16. Applying offer [1,2,10] covers one of item 0 and two of item 1 for 10, leaving need [2,0] which costs 2·2 = 4. Total 10 + 4 = 14, which is the cheapest.
Because each distinct remaining-needs state is solved once, the work is bounded by the number of states times the number of offers.