Optimize Coupon Selection Under a Twenty-Point Budget

Problem Statement

You are building a checkout discount engine for a grocery store. Shoppers have a loyalty point balance of up to 20 points and a collection of coupons they can activate. Each coupon costs a certain number of points to activate.

You are given:

• A list of items, where each item has an id, category, and price (in cents).
• A list of coupons, where each coupon has:
  • id (unique string)
  • level: "ITEM" (applies to a specific item target_id) or "CATEGORY" (applies to all items in target_category)
  • discount_type: "PERCENT" or "FIXED"
  • value: integer percent (1–100) or fixed amount in cents
  • max_savings: integer cap in cents on the total discount this coupon can provide across all items it touches (-1 if uncapped)
  • cost: integer point cost (1 <= cost <= 20)
• budget: integer point budget (always 20)

Discount & Stacking Rules

1. At most one ITEM coupon and at most one CATEGORY coupon can apply to any single item.
2. When both apply to an item, the ITEM coupon applies first against the item's original price. The CATEGORY coupon then applies to the remaining balance of the item's price.
3. Percentage discounts round down to the nearest cent (floor(price * value / 100)).
4. An item's price cannot be discounted below 0 cents.
5. If a coupon has max_savings != -1, the total discount provided by that coupon (summed across all applicable items) cannot exceed max_savings.
6. Total point cost of all activated coupons cannot exceed budget.

Optimization Objective & Tie-Breaking

Find the subset of coupons that maximizes total monetary savings in cents. If multiple subsets yield the same maximum savings:

1. Choose the subset with the lower total point cost.
2. If still tied, choose the subset whose sorted list of coupon IDs is lexicographically smaller.

Return a tuple/list: (max_savings_in_cents, points_used, list_of_activated_coupon_ids) with coupon IDs sorted alphabetically.

Interface

def optimize_coupons(
    items: list[dict],
    coupons: list[dict],
    budget: int = 20
) -> tuple[int, int, list[str]]:
    pass

Input Constraints

• 1 <= len(items) <= 50
• 1 <= len(coupons) <= 15
• 1 <= item["price"] <= 50000 (cents)
• 1 <= coupon["cost"] <= 20
• budget = 20

Examples

Example 1

items = [
    {"id": "i1", "category": "dairy", "price": 1000},  # $10.00
    {"id": "i2", "category": "dairy", "price": 500},   # $5.00
]
coupons = [
    {"id": "c1", "level": "ITEM", "target": "i1", "discount_type": "FIXED", "value": 200, "max_savings": -1, "cost": 5},
    {"id": "c2", "level": "CATEGORY", "target": "dairy", "discount_type": "PERCENT", "value": 20, "max_savings": 250, "cost": 10},
]
budget = 20

Output: (410, 15, ["c1", "c2"]) Explanation:

• c1 costs 5 points, saves 200 cents on i1. i1 remaining price is 800 cents.
• c2 costs 10 points (20% off dairy). On i1, 20% of 800 = 160 cents. On i2, 20% of 500 = 100 cents. Potential category savings = 260 cents, but capped at max_savings = 250 cents.
• Total savings = 200 + 250 = 450 cents? Wait: without c1, c2 saves 20% of 1000 (200) + 20% of 500 (100) = 300 capped at 250. With c1 + c2, c1 saves 200, c2 saves min(250, 160 + 100) = 250. Total = 450 cents. Points used = 15. Output: (450, 15, ["c1", "c2"]).

Example 2

items = [{"id": "i1", "category": "bakery", "price": 400}]
coupons = [
    {"id": "c_a", "level": "ITEM", "target": "i1", "discount_type": "PERCENT", "value": 50, "max_savings": -1, "cost": 10},
    {"id": "c_b", "level": "ITEM", "target": "i1", "discount_type": "FIXED", "value": 200, "max_savings": -1, "cost": 10}
]
budget = 20

Output: (200, 10, ["c_a"]) Explanation: Both coupons save 200 cents and cost 10 points. Since only one item coupon can apply to i1, they cannot stack. Both achieve 200 cents savings at 10 points; "c_a" is chosen because ["c_a"] < ["c_b"] lexicographically.