Optimize Coupon Selection Under a Twenty-Point Budget

Choose which shopping-cart coupons to activate to maximize total savings under a 20-point budget. An item-specific coupon costs 2 points to activate, and a category-wide coupon costs 5 points. ### Requirements and Constraints Items have a name, category, and price in integer cents. Available coupons specify an item name or category and a percentage reduction. There is at most one item coupon per item name and one category coupon per category. A selected coupon applies to every matching cart row. All activated discounts follow these rules: item discounts apply before category discounts, remaining-price factors multiply, unrounded total savings on an item are capped at 80 percent, and only the final per-item discount is rounded to cents using ties-to-even rounding. Then those rounded savings are summed across the cart. Unmatched coupons provide no savings. Explain an exact baseline algorithm and how you would improve it. Return a selection of coupon records and the total points used; more than one selection may achieve the same optimal savings, so this is a conceptual optimization discussion rather than a console with an invented tie-break rule. ### Clarifying Questions - How many items, categories, and available coupons must the implementation support? - Does every item name belong to one category, or can an item-specific coupon affect rows in several categories? - Are any optimal selections acceptable, and is using fewer points a separate objective or only a budget constraint? - How are percentages represented so the final rounding rule can be implemented consistently? ```hint The value of a coupon depends on what is already selected An item coupon and a category coupon can overlap on the same row. Their combined benefit is not generally the sum of their separate benefits because of stacking, the cap, and rounding. ``` ### What a Strong Answer Covers - A reusable, exact savings evaluator matching the stated stacking, cap, and per-item rounding rules. - A feasible exact search baseline that checks the 20-point budget and includes choosing no coupons. - An explanation of why ordinary additive coupon-value knapsack or greedy savings-per-point can be wrong. - A justified improvement, with the additional assumptions needed for grouping or dynamic programming. - Reconstruction and validation of the selected coupon records, point cost, and achieved savings. - Honest treatment of multiple optima and of heuristics that do not guarantee the best savings. ### Follow-up Questions 1. Why can a coupon's standalone savings overstate its additional benefit after another coupon is activated? 2. Under what condition can categories be optimized independently and then combined by budget? 3. How would you verify the optimized solver against a simpler method on small inputs?