Why is optimal substructure alone not enough to justify a greedy algorithm, and what else is required?

## Two properties, often confused **Optimal substructure** means: an optimal solution to the whole problem contains, inside it, optimal solutions to the subproblems it decomposes into. Equivalently — once you fix the first decision, the best completion of the rest is itself an optimal solution to the smaller problem left behind. This is what makes a recursive formulation of the objective valid at all. **The greedy-choice property** means: for every input, there exists at least one optimal solution that *begins with the choice your rule makes*. Note the quantifier carefully — *some* optimal solution, not *every* one. Commit to the choice and you may throw away other optimal solutions, but you never throw away all of them. Optimal substructure is the weaker, shared condition. Dynamic programming lives on it too: it decomposes exactly the same way, but because it has no safe first move, it must enumerate the candidate choices at each step and keep the best, paying time and memory to avoid committing. Greedy is what you get when you can prove the enumeration is unnecessary because one branch always suffices. So the diagnostic question is never "does this decompose?" — almost every optimization problem does. It is "is the first move safe?" ## A worked contrast: divisible bulk versus indivisible crates A delivery van has **10 kg** of free capacity. There are three goods: | Item | Weight | Value | Value per kg | |---|---|---|---| | A | 6 kg | 30 | 5.0 | | B | 5 kg | 24 | 4.8 | | C | 5 kg | 24 | 4.8 | The greedy rule under test: **take the highest value-per-kilogram first.** *If the goods are divisible bulk* (grain, sand, cable by the metre), greedy takes all of A for 30, then 4 kg of B for 19.2, totalling **49.2** — and that is optimal. The safe-move argument works: if some optimal load contains less than the maximum possible amount of the densest good, you can substitute density-for-density and never lose value, so an optimal solution starting with "as much of A as fits" always exists. *If the goods are indivisible crates*, that substitution is illegal — you cannot shave 1 kg off a crate. Greedy takes A (30), then has 4 kg left, and neither B nor C fits whole, so it returns **30**. The optimum is B + C = exactly 10 kg for **48**. The greedy answer is off by 60%. Here is the point that carries the whole question: **both versions have optimal substructure.** In both, once you fix what happens to the first item, the best completion is an optimal packing of the remaining capacity with the remaining items. The decomposition is identical. Only the *safety of the first commitment* differs — and that alone decides greedy versus dynamic programming. ## How to state the property for your own rule Write the claim explicitly, in the form: *for every input, there is an optimal solution whose first selected element is the one my rule picks*. Then identify what the remaining subproblem is after that pick — if it is not a smaller instance of the same problem, the recursion does not close and neither technique applies cleanly. Two sentences, said out loud, are what separates "greedy feels right here" from an answer an interviewer accepts. Be honest about the direction of the claim as well. It is an existence claim about *some* optimum, not a claim that every optimum starts that way, and not a claim that your rule's choice is unique. Overstating it to "every optimal solution begins with my choice" is a common slip, and it is usually false even when greedy is correct — ties alone create optimal solutions that start differently. ## What to do when the property fails You keep the substructure and give up the commitment: enumerate the choices at each step and memoize or tabulate the subproblem answers. You trade a single pass for a table, buying correctness with time and memory. The reverse move is also worth knowing: sometimes a problem that resists a safe move acquires one after a change of representation — most often after sorting by the right key, which is why so many correct greedy algorithms have the shape "sort, then one linear pass". Finally, resist the seductive shortcut of validating a greedy rule by examples. Agreement on the cases you happened to try is evidence about those cases only; the property is a statement about *every* input, and it is a claim you argue, not one you sample.