A checkout must pick discount bundles over a cart — how do you decide greedy, divide-and-conquer or DP?

## Drive the choice from structure, in a fixed order The three paradigms are not three styles to pick by taste. Each one is licensed by a specific property, and asking about those properties in order gets you to an answer you can defend. | Question about the problem | If yes | | --- | --- | | Can the input be cut so no bundle spans the cut? | Divide-and-conquer: solve pieces independently, add, no table | | Is the locally best bundle always in *some* optimal basket? | Greedy — once you can prove it | | Do different bundle orders reach the same remaining cart? | A recurrence over that remaining cart, tabulated | ## Step one: look for independence A checkout cart is often not one problem. If bundles are scoped per merchant, per category, or per shipment, then items in different groups can never appear in the same bundle, and the groups do not interact at all. That is textbook divide-and-conquer: split, solve, combine by addition. The subproblems are disjoint, so there is nothing for a table to remember, and adding one buys nothing but memory. This step is worth doing first because it is the cheapest possible win and it is frequently available in real systems. It also shrinks whatever remains: if only one group is entangled, you can afford a much more expensive method on that group alone. ## Step two: test the greedy choice honestly The tempting rule is "apply the bundle with the largest saving that the cart still supports, then repeat". The property it needs is that some optimal basket of bundles contains that first bundle. It usually fails, and the failure has a recognisable shape: the big bundle consumes items that two smaller bundles would each have needed, and the two together saved more. Any structure where bundles *compete for the same items* invites this. So either you can argue the property — a total ordering on bundles under which the top choice is never regretted, which does exist for some pricing schemes — or you cannot, and greedy is off the table as a correctness claim. A rule you cannot justify may still ship as a heuristic, but that is a separate decision made with error measurements, not the same as choosing greedy as *the* paradigm. ## Step three: check that the state compresses If bundles compete, then different orders of applying bundles land on the same remaining cart, and that repetition is exactly the overlap that a table exploits. But overlap alone is not enough to make dynamic programming *practical*. The deciding question is how big the state space is. - If bundles are defined over a small number of item **categories**, the remaining cart is a vector of counts — a few dimensions, each bounded by the quantity in the cart. That is a modest table, and the recurrence "best saving on this count vector" is straightforward. - If bundles are defined over arbitrary sets of individually distinct items, the remaining cart is an arbitrary subset. The number of states is exponential in the number of distinct items, and no table survives a real cart. This is the step candidates skip, and it is the one that separates a senior answer from a textbook one. Overlap tells you a table *would* help; state-space size tells you whether you can afford one. When it does not compress, the real answer is branch-and-bound or beam search with a deadline and a best-so-far answer, with the exact method reserved for small carts. ## Say what you would measure before committing Before choosing, get the numbers that decide it: the distribution of cart sizes, how many distinct bundle definitions are active, whether bundles overlap in items at all, and what the checkout latency budget is. A shop where 99% of carts hold under a dozen line items and bundles are per-category can run the exact recurrence comfortably; the same code on a wholesale order of thousands of lines will not. That is why the answer is often *both*: exact below a size threshold, a fallback above it, with the threshold picked from the latency budget rather than from a feeling. ## The two failure modes to name out loud Announcing "this is dynamic programming" because the problem is an optimisation problem is the first. Optimisation is not the test; repeated subproblems over a compact state are. Assuming independence because the pieces *look* separable is the second. If one bundle can span two groups you had assumed were independent, the divide-and-conquer decomposition is silently wrong — and unlike a useless memo, this failure changes the answer rather than just the running time. Check the bundle definitions for cross-group reach before you cut.