# Shopping basket: manual plan versus exact minimum

## Result

The cheapest legal checkout is **$56.70**, compared with my previously saved hand-calculated plan of **$58.30**. The manual plan costs **$1.60 more**, or **2.74% of its $58.30 spend**. The full basket costs $83.00 at shelf prices and $74.70 after the member discount.

| Plan | Receipts | Member subtotal | Coupon savings | Final cost |
|---|---:|---:|---:|---:|
| Hand-calculated, saved before code | 2 | $74.70 | $16.40 | $58.30 |
| Exact minimum | 2 | $74.70 | $18.00 | **$56.70** |

## Products and rules

The basket contains one each of ground coffee (CF, $19), cereal (CE, $8), pasta (PA, $6), detergent (DE, $27), toothpaste (TP, $9), and shampoo (SH, $14). Rule R001 reduces each shelf price by 10% for the member. Rules R002–R100 are 99 separately numbered single-use coupons in nine campaigns, each with eleven minimum-spend tiers. The complete 100-rule table, product definitions, eligibility tests, and stacking mechanics are in `basket-and-100-rules.md`. Each receipt can use at most one coupon; a coupon ID cannot be reused across receipts.

## Plans and receipt arithmetic

**Manual plan, $58.30**, documented in `manual-checkout-plan.md` before the notebook search:

| Receipt | Items | Post-member subtotal | Coupon | Pay |
|---|---|---:|---|---:|
| 1 | DE, TP, SH, PA | $50.40 | R099, $12 off when a large basket reaches $50 | $38.40 |
| 2 | CF, CE | $24.30 | R049, $4.40 off the coffee-and-cereal bundle at $20 | $19.90 |

**Exact plan, $56.70**:

| Receipt | Items | Post-member subtotal | Coupon | Pay |
|---|---|---:|---|---:|
| 1 | CF, DE, SH | $17.10 + $24.30 + $12.60 = $54.00 | R099, $12 off; three items and $54 ≥ $50 | $42.00 |
| 2 | CE, PA, TP | $7.20 + $5.40 + $8.10 = $20.70 | R093, $6 off; three items and $20.70 ≥ $20 | $14.70 |

The manual split used a $4.40 breakfast-bundle coupon on its second receipt. Moving CF into the other receipt and TP into the second creates two qualifying three-item baskets, allowing R093 to save $6.00 on the second receipt. R099 still saves $12.00 on the first receipt.

## Reproduction and optimality check

The notebook ran the standard-library Python code saved as `exact-checkout-search.py` (Python 3.10+). It represents money in integer cents, generates the 99 coupon entries from the exact campaign schedules in the rule book, and asserts that R001 plus those coupons gives 100 rules. It enumerates all **203 set partitions** of six distinct items. For each partition it uses dynamic programming to assign distinct coupon IDs to receipts, allowing one or no coupon per receipt; the best legal assignment across all partitions saves $18.00.

A second notebook calculation drops the one-use-per-coupon restriction and computes the best coupon saving over all item partitions with a simpler subset dynamic program. This relaxation can only increase possible savings, yet it also returns **$18.00**. Since the legal two-receipt plan attains $18.00, the true minimum is $74.70 − $18.00 = **$56.70**. The notebook additionally checked item coverage, no overlapping receipts, distinct coupon IDs, thresholds, item conditions, and receipt arithmetic.

This synthetic scenario assumes free membership, unlimited receipt splitting, no tax or shipping, and no discounts beyond its 100 specified rules. Actual store systems may restrict multiple transactions or coupon eligibility differently.
