Optimize Coupon Selection Under a Twenty-Point Budget

You are given a cart of line items. For each line item, the available data are its item name, its category, and its price expressed as an integer number of cents. You are also given a set of coupons. A coupon is either locked to a single item name or scoped to an entire category. Every coupon specifies a percentage reduction. No item name may have more than one coupon associated with it, and no category may have more than one coupon associated with it. Activating an…