Greedy Algorithm
1. Overview
A. Definition
A Greedy Algorithm is a problem-solving strategy that attempts to reach the global optimum by, at each step, making the locally optimal choice that looks best at that moment and never revoking a decision once made. It guarantees a correct answer only for problems where the greedy choice property (a choice can lead to the global optimum) and optimal substructure hold.
A greedy algorithm formalizes the extremely simple intuition of "grab whatever is most advantageous right now and never look back." Picking the largest-denomination coin first when giving change is a typical example: without enumerating every combination, people know from experience that using larger coins first reduces the number of coins. Because the greedy strategy "decides on the best in sight without viewing the whole," it is concise to implement and usually finishes in polynomial time (often O(n log n)), making it overwhelmingly faster than brute force or dynamic programming. This very speed makes greedy algorithms attractive, but it also always carries the legitimacy question of "is a succession of local optima truly the global optimum?"
The value and risk of greedy algorithms are two sides of the same coin. For problems that satisfy certain conditions (minimum spanning tree, Huffman coding, fractional knapsack, job scheduling, etc.) greedy yields a provably optimal solution, but when the conditions break it produces a plausible yet clearly wrong answer. Hence the core competence of a professional engineer dealing with greedy algorithms lies in the design judgment of "first determining whether the problem is solvable by greedy, arguing the legitimacy of the greedy choice if it is, and switching to dynamic programming or brute force if it is not."
B. Background and Necessity
Many optimization problems have a number of feasible solutions that explodes exponentially with input size. For example, in what order to process n jobs, or which of n items to place in a knapsack, each has on the order of n!·2ⁿ cases, so brute force that enumerates every case becomes practically impossible as soon as n grows a little. Dynamic programming (DP) suppresses this explosion to polynomial time by storing overlapping subproblems, but when the state space is large, memory and time remain burdensome. At this point a demand arises for "a shortcut that reaches the correct answer without considering every case," and when a problem has a particular structure, the greedy algorithm provides that shortcut.
What matters here is that whereas brute force and DP are passive strategies that "somehow sweep through all possibilities," greedy is an active strategy that "understands the structure of the problem and never even looks at most of the possibilities from the outset." This difference goes beyond a mere speed-up: it also means greedy holds only when one has insight into the order inherent in the problem (sortable priorities, exchangeable elements, matroid structure). Designing a greedy algorithm is therefore precisely the task of uncovering "which property of this problem makes exhaustive search unnecessary," and this is the area that most directly tests an algorithm designer's analytical power.
Moreover, many real systems demand solutions that are "not perfect but fast and good enough" under real-time and resource constraints. A network router must update routes on a millisecond scale, an OS scheduler must instantly pick the next process to run at every moment, and a data compressor must generate codes as it passes through a stream. In such environments, a greedy strategy that makes immediate local decisions on incoming information is structurally more suitable than DP that recomputes the whole. Furthermore, for problems that are NP-hard and cannot be solved optimally in polynomial time (set cover, traveling salesman, etc.), greedy—though not optimal—provides practical solutions with a guaranteed approximation ratio, bridging theory and practice. Thus the greedy algorithm stands on a dual necessity: "a fast optimizer that conditionally guarantees correctness" and "a reliable approximator for hard problems."
2. Operating Principle and Legitimacy Conditions of Greedy Algorithms
The two core conditions for a greedy algorithm to work correctly are the greedy choice property and optimal substructure. Only when both hold is the leap that "a chain of local optima is the global optimum" justified.
flowchart TB
PROB["Optimization problem"] --> Q1{"Greedy choice property holds?"}
Q1 -->|"No"| DPFULL["Switch to DP / brute force"]
Q1 -->|"Yes"| Q2{"Optimal substructure holds?"}
Q2 -->|"No"| DPFULL
Q2 -->|"Yes"| GREEDY["Apply greedy algorithm (optimality guaranteed)"]
GREEDY --> PROOF["Legitimacy proof: exchange argument / matroid"]
The greedy choice property is the property that "at least one global optimum can be constructed so as to include the greedy choice at each step." That is, the local best grabbed now must be capable of being part of the final optimum. The standard technique for showing this rigorously is the exchange argument. Assuming an arbitrary optimum, if the element greedy chose is missing from that solution, one shows that swapping it for another element does not worsen the solution, proving that an optimum including the greedy choice must exist. For instance, in the activity selection problem, the reason the greedy of "choosing the activity that finishes earliest first" is correct is that replacing the first activity of any optimum with the earlier-finishing greedy activity does not reduce the activities selectable thereafter. The exchange argument is the most universal tool for handling the legitimacy of greedy algorithms, so it must be mastered.
Looking at the exchange argument a little more concretely, its skeleton is to show that "if the greedy solution and the optimal solution differ, transforming the optimal solution little by little toward the greedy solution does not degrade quality." If the first choice differs, replace the optimum's first choice with greedy's first choice, confirm it is still optimal, and repeat this process for the second and third choices. Once all choices have been replaced, the optimum becomes completely identical to the greedy solution, so one arrives at the conclusion that "the greedy solution is also optimal." Proving that this inductive replacement harms quality at no step is the heart of the exchange argument, and only when that proof is possible can greedy be adopted with confidence.
Optimal substructure is the property that "an optimal solution to the problem is composed of optimal solutions to subproblems," meaning that after greedy fixes one element, the remaining subproblem must also be solvable optimally by the same greedy strategy. Dynamic programming shares this property too; the decisive difference between the two techniques lies in how the subproblems are solved. DP obtains and compares/combines the solutions of several subproblems, whereas greedy "narrows the subproblem to just one with a single greedy choice" and follows only that one branch down. It is precisely this "reduce the options to one and never look back" that makes greedy faster than DP, but it also bears the risk that if the choice is wrong, the whole thing goes awry.
flowchart LR
S0["Whole problem"] --> C1["Greedy choice 1 (local optimum)"]
C1 --> S1["Reduced subproblem"]
S1 --> C2["Greedy choice 2"]
C2 --> S2["Smaller subproblem"]
S2 --> DOTS["..."]
DOTS --> SOL["Global optimum"]
C1 -. "never look back (irrevocable)" .-> C1
A representative counterexample where legitimacy is not guaranteed is the change-making problem. If the coin denominations form a canonical system like {1, 5, 10, 25}, the "largest-first" greedy guarantees the minimum number of coins, but in the {1, 4, 6} system, when giving change of 8, greedy takes 6+1+1=3 coins whereas the optimum is 4+4=2. The fact that the legitimacy of greedy collapses when the same problem's input conditions (coin system) change vividly shows that legitimacy must be verified before using a greedy algorithm. Applying greedy because it "looks intuitively correct" without verification is a typical design error.
The lesson of this counterexample is not simply that "greedy is sometimes wrong," but that it reveals a more general structural limitation called the local optimum trap. Because greedy chases only the immediate gain without seeing the ripple its current choice will have on the future, it fundamentally cannot explore a path where "take a small loss now for a large gain later." In the {1, 4, 6} system, the instant you grab 6 you can fill the remaining 2 only with 1+1—that is exactly this trap. In contrast to dynamic programming, which stores and compares all options to capture such "delayed gains," greedy discards that branch entirely. Verifying greedy's legitimacy is therefore essentially the task of showing that "no local optimum trap exists in this problem," and the exchange argument is precisely the tool that proves that absence.
3. Design Procedure and Representative Algorithms
For a problem equipped with the two conditions above, designing a greedy algorithm generally follows a common procedure. First define the optimization target (objective function), then set the greedy choice criterion (sort key) for each step, accumulate the solution while checking that the choice does not violate constraints, and finally prove legitimacy via the exchange argument or the like. Since many greedy algorithms take the form of "sort by a particular criterion then traverse from the front," the dominant cost is often the O(n log n) of the sort (see [[sorting-algorithms]]).
The most creative and difficult step in this procedure is setting the greedy choice criterion. The remaining steps (constraint checking, solution accumulation) are mechanical, but "by what criterion to pick the best" differs per problem and, if chosen wrongly, leads straight to a wrong answer. Thus a seasoned designer sets up several plausible candidate criteria, actively hunts for small counterexamples against each to filter them out, and establishes legitimacy via the exchange argument only for the criteria that produce no counterexample. The flowchart below diagrams this common procedure.
flowchart TB
START["Define problem / objective function"] --> SORT["Sort candidates by greedy criterion"]
SORT --> LOOP{"Any candidates left?"}
LOOP -->|"Yes"| PICK["Select best candidate per criterion"]
PICK --> FEASIBLE{"No constraint violation?"}
FEASIBLE -->|"Yes"| ADD["Add to solution set"]
FEASIBLE -->|"No"| SKIP["Skip"]
ADD --> LOOP
SKIP --> LOOP
LOOP -->|"No"| PROOF["Return solution after legitimacy check"]
A. Activity Selection and Job Scheduling
The activity selection problem is that of choosing the maximum number of mutually non-overlapping activities from a set of activities with given start and finish times. The greedy criterion is "select the activity that finishes earliest first," then repeatedly pick the next activity that does not overlap the selected one. This criterion is correct because the earlier an activity finishes, the more time remains afterward and the greater the room to pack more activities. For example, if a single meeting room has eleven requests (1–4), (3–5), (0–6), (5–7), (3–9), (5–9), (6–10), (8–11), (8–12), (2–14), (12–16), the finish-time greedy assigns the four (1–4)→(5–7)→(8–11)→(12–16), achieving the optimum. Interestingly, other plausible criteria such as "shortest activity first" or "earliest-starting activity first" have counterexamples and fail to guarantee optimality, an important lesson showing that which greedy criterion you choose governs legitimacy. This principle applies broadly to practical problems of packing non-overlapping jobs into a single resource as much as possible: CPU scheduling, lecture-room and facility reservation, ad-slot placement. One should also note that in a variant where each activity carries a value (weight) and one must "maximize the sum of values, not the count," the simple finish-time greedy no longer guarantees optimality and turns into a dynamic programming problem called weighted interval scheduling. This reveals that the hidden premise "every activity has equal value" was propping up greedy's legitimacy, reconfirming the recurring lesson that when the premise changes the technique must change too.
B. Fractional Knapsack Problem
The fractional knapsack is the problem of placing items into a knapsack of capacity W to maximize the sum of values, where items can be split. The greedy criterion is "fill from the item with the highest value per unit weight (value/weight), and for the last item, split it to fit the remaining capacity." For example, with a 50 kg knapsack and three items (value 60, weight 10), (value 100, weight 20), (value 120, weight 30), the unit values are 6, 5, 4 respectively, so pack item 1 (10 kg·60)→item 2 (20 kg·100) whole and item 3 for the remaining 20 kg (2/3), obtaining value 60+100+80=240. Because items can be split, the unit-value order is itself the optimal order, so greedy yields exactly the optimum.
However, when the condition changes to the 0/1 knapsack where items cannot be split, the same greedy fails to guarantee optimality. In a configuration like capacity 10 kg with (value 60, weight 10), (value 70, weight 10)..., "picking just one in unit-value order" may miss a more valuable combination. The 0/1 knapsack must weigh the "include/exclude" combinations, so the greedy choice property breaks and it must be solved by dynamic programming (or branch and bound). This stark contrast between fractional and 0/1 knapsack is a representative example frequently used in professional-engineer answers, showing that a single constraint—"can it be split?"—is the decisive factor dividing greedy's legitimacy (see [[dynamic-programming]]).
C. Huffman Coding
Huffman coding is a greedy algorithm that generates variable-length prefix codes according to each character's frequency to compress data losslessly. The greedy criterion is "repeatedly merge the two lowest-frequency nodes": at each step it takes out the two minimum-frequency nodes, binds them into a merged node, and builds the binary tree bottom-up. It assigns short codes to frequent characters and long codes to rare ones so that the average code length approaches the information entropy. For example, if the frequencies of characters a·b·c·d·e·f are 45·13·12·16·9·5, Huffman first merges the rarest f(5)·e(9) into 14, then merges the next-smallest c(12)·b(13) into 25, building the tree bottom-up. In the completed tree a receives a 1-bit code and the rest 3–4 bit codes, shrinking to about 224 bits, smaller than a fixed-length 3-bit code (about 300 bits total)—the effect of concentrating short codes on frequent characters. The legitimacy of this "minimum-frequency-first" greedy is also proved by the exchange argument (in an optimal tree, the two deepest leaves can be swapped for the two lowest-frequency characters without loss), and using a min-heap (priority queue) it runs in O(n log n). Huffman coding is actually embedded in the entropy coding stage of a wide range of compression standards such as JPEG, MP3, ZIP (DEFLATE), and PNG, counting as a prime example of a greedy algorithm operating at the heart of industry standards.
D. Greedy on Graphs: Minimum Spanning Tree and Dijkstra
Greedy is a core design strategy for graph problems too. Kruskal's algorithm for the minimum spanning tree (MST) is the greedy of "adopt edges from the smallest weight, as long as they create no cycle," and Prim's algorithm is the greedy of "absorb, one by one, the vertex that connects most cheaply to the current tree." Both have optimality guaranteed by the graph's cut property—"the minimum-weight edge crossing any cut is necessarily included in some MST." Kruskal sorts edges and checks cycles with Union-Find, running in O(E log E), while Prim uses a min-heap, running in O(E log V); they are used for minimizing communication-network cabling, power-grid design, clustering (single-linkage clustering), and more.
The fact that Kruskal and Prim build up the same MST in different orders shows the flexibility of the greedy strategy. If Kruskal is the global view of "sweeping all edges in weight order and gradually merging pieces of a forest," Prim is the local-growth view of "starting from one vertex and growing the tree layer by layer." Either way, each step's greedy choice (minimum edge, minimum-connecting vertex) is guaranteed safe by the cut property, so the optimality of the result is identical; the choice splits according to graph density, with Prim (adjacency-matrix based O(V²)) favored on dense graphs with many edges and Kruskal on sparse graphs. Meanwhile, the Dijkstra algorithm of [[shortest-path]] discussed earlier is also the greedy of "fixing the unfixed vertex with the minimum tentative distance," where the condition of non-negative weights props up the legitimacy of the greedy choice. Interestingly, Prim and Dijkstra have almost the same skeleton of "absorb the vertex nearest to the current set," differing only in that Prim uses 'the edge weight itself' as its criterion while Dijkstra uses 'the cumulative distance from the source.' That a considerable portion of graph algorithms stand on the greedy paradigm thus well demonstrates the design-level universality of the greedy strategy.
4. Comparison: Greedy · Dynamic Programming · Brute Force
Greedy, dynamic programming, and brute force—the three representative paradigms for solving optimization problems—diverge in "how many cases they weigh" and "to what extent they guarantee correctness." The table below organizes the differences, but the reason they arise is rooted in how each technique handles subproblems.
| Category | Greedy Algorithm | Dynamic Programming | Brute Force |
|---|---|---|---|
| Core strategy | Local-optimal choice, never revoke | Store/combine subproblem solutions | Enumerate all cases |
| Subproblem handling | Narrow to one by choice | Compare all solutions | Exhaustive branch search |
| Optimality guarantee | Only when conditions hold | Always (for that structure) | Always |
| Time complexity | Usually O(n log n) | Polynomial (states × transitions) | Exponential (n!·2ⁿ) |
| Memory | Small | As large as the state table | Small (recursion stack) |
| Suitable situation | Greedy choice property holds | Overlapping subproblems · optimal substructure | Small scale · correctness absolute |
Greedy and dynamic programming are close in that both require optimal substructure, but the presence or absence of the greedy choice property separates them. When this property holds, "each step's choice can be fixed immediately without comparison," so greedy is exponentially faster than DP and uses almost no memory. Conversely, when this property is absent (like the 0/1 knapsack), greedy is wrong and DP must store and compare all options. The practical implication, therefore, is "choose greedy if the greedy choice property is proved, DP if there are only overlapping subproblems, and brute force if both are uncertain and the input is small." In particular, overlooking the point that even for the same problem, the suitable technique changes when the constraints change (fractional knapsack ↔ 0/1 knapsack) creates a fatal flaw that looks like the right answer on the surface but diverges on certain inputs.
Feeling the complexity difference numerically makes the gap between the three paradigms clear. Solving a 0/1 knapsack with input size n=40 by brute force requires weighing 2⁴⁰≈1 trillion branches, taking tens of minutes or more even on a modern CPU, but with capacity W around 1,000, dynamic programming fills only 40×1,000=40,000 states and finishes in milliseconds. Meanwhile, for a fractional knapsack where the same items can be split, greedy needs only the O(40 log 40)≈200-odd operations of sorting by unit value. This dramatic cost reduction of "brute-force exponential → DP polynomial → greedy near-linear" is bought, at each step, at the price of a stronger assumption about the problem structure—DP requires optimal substructure, and greedy additionally requires the greedy choice property. There is no free lunch, and this principle that faster algorithms have stricter applicability conditions underlies paradigm selection.
To summarize the relationship of the three techniques in one sentence, brute force is "the slow but always-correct baseline," dynamic programming is "a safe optimizer that compresses brute force to polynomial by removing redundancy," and greedy is "the fastest optimizer that, premised on a particular structure, reduces even DP to a single branch." Real systems often combine these—for example, branch and bound for the 0/1 knapsack prunes the brute-force search space with a greedy upper bound (the fractional knapsack solution), boosting practical performance.
5. Advanced: Matroid Theory and Approximation Algorithms
The deepest theoretical answer to "when does greedy guarantee optimality" lies in matroids. A matroid is a structure where a finite set and a collection of its subsets (independent sets) satisfy heredity and the exchange property, and the theorem (Rado-Edmonds) that "if a problem is expressed as a weighted matroid, the greedy algorithm always guarantees an optimal solution" holds. The fundamental reason the minimum spanning tree obtains the optimum via greedy (Kruskal) also comes from the graphic matroid structure of the graph. In that this theory mathematically elucidates "what is a sufficient condition for greedy to be correct" beyond "does greedy intuitively seem right," it is a powerful framework that generalizes individual exchange arguments. That said, not every greedy success is explained by matroids (activity selection and such hold under weaker conditions), and a matroid is a sufficient, not a necessary, condition. The practical implication of matroid theory is that when meeting a new optimization problem, one can structurally pre-screen the applicability of greedy by checking "does this problem's solution set satisfy heredity and the exchange property?" It is also known that while the intersection of two matroids (matroid intersection) is still solvable in polynomial time, the intersection of three or more crosses into NP-hard, so how many matroid constraints a problem can be reduced to becomes a theoretical yardstick for gauging the applicability limits of greedy and polynomial algorithms.
Another important stage for greedy is approximation algorithms. Because NP-hard optimization problems are believed to be unsolvable optimally in polynomial time, in practice one compromises with an approximate solution that "is not optimal but is guaranteed to be within a certain ratio of the optimum." Notably, in the Set Cover problem, the greedy of "repeatedly selecting the set that covers the most still-uncovered elements" guarantees an ln n approximation ratio, which is known to be theoretically nearly the best possible ratio under the P≠NP assumption. The nearest neighbor greedy for the traveling salesman problem (TSP) and the longest processing time first (LPT) greedy for workload balancing are also practical methods with guaranteed approximation ratios. Thus greedy is not only "an exact optimizer" but also "a reliable approximator for hard problems," implementing the typical trade-off of yielding some correctness in exchange for polynomial time and performance guarantees.
The reason greedy is especially preferred in approximation algorithms lies in its simplicity and analyzability. Alternatives such as local search, genetic algorithms, and integer programming may yield better solutions but make it hard to guarantee convergence and running time in advance, whereas greedy approximation is simple to implement yet can mathematically prove a worst-case guarantee of "within a few times the optimum." For example, in the problem of distributing jobs across multiple machines to minimize completion time, the LPT (longest job first) greedy is proved to be within (4/3 − 1/3m) of the optimum, enabling a clear quality promise in practice like "no matter how bad, this schedule is no worse than 33% above the optimum." Whether such a guarantee exists is the decisive factor dividing whether an algorithm can be trusted and adopted in an operational environment, and this is precisely the background for greedy approximation becoming the default strategy of countless schedulers and batch systems.
A recent trend drawing attention is greedy in online and streaming environments. In situations where the entire input cannot be seen in advance and data flows in (online ad allocation, real-time matching, streaming set cover), greedy's never-look-back nature holds a naturally good fit. Just as the RANKING algorithm for online bipartite matching achieves a 1−1/e competitive ratio, the competitive analysis of greedy-based online algorithms is an active research area. Moreover, the result that greedy guarantees a 1−1/e approximation in submodular function maximization provides the theoretical foundation for greedy in modern AI and data applications such as recommender systems, data summarization, and sensor placement, showing that greedy algorithms are expanding beyond classical data structures into the latest fields.
6. Considerations and Implications
When moving the principles, cases, and theory of greedy algorithms examined so far into actual system design, a professional engineer must judge comprehensively—weighing legitimacy, applicability conditions, and the relationship with alternatives—rather than choosing greedy simply because it is "fast." The following are the key considerations in that judgment.
Beware of applying greedy without a legitimacy proof. Greedy must not be adopted merely because it "looks intuitively correct"; one must verify the greedy choice property and optimal substructure via the exchange argument or matroid structure. Since cases where greedy is wrong when conditions change—like change-making and the 0/1 knapsack—are common, in the requirements-analysis stage one should proactively check "does this problem really solve by greedy, are there counterexamples?" to exclude "plausible but wrong" solutions.
Switch techniques according to problem conditions and constraints. For the same knapsack problem the suitable technique splits into greedy (fractional) and DP (0/1) depending on 'can it be split,' and the presence of negative edges in a graph governs the applicability of Dijkstra (greedy). The design judgment is key: diagnose the conditions and choose the right paradigm—greedy if the greedy choice property holds, DP if there are only overlapping subproblems, brute force if the input is small and correctness is absolute.
The choice of greedy criterion (sort key) determines legitimacy. Just as 'finish-time first' is optimal but 'shortest activity first' has counterexamples in activity selection, even for the same problem, which criterion you make the greedy choice by divides right from wrong. Therefore one must compare several candidate criteria, review the counterexamples of each, and adopt only the criterion whose legitimacy is proved; skipping this process breeds a latent defect that fails only on certain inputs.
Tune the trade-off between approximation and correctness to service requirements. For NP-hard problems a greedy approximation rather than the optimum is the realistic choice, and it is important to know the guaranteed ratio, like set cover's ln n approximation. In systems with large real-time and resource constraints (routing, scheduling, streaming), a 'fast and good enough' greedy solution may be more reasonable than 'perfect optimality,' so judge the balance point of correctness, responsiveness, and resources from an SLA and cost perspective.
Verify implementation pitfalls and boundary cases. Since greedy is usually a sort-then-traverse structure, one must specify sort stability and tie-handling rules to get reproducible results. Small implementation errors—omitting path compression in Kruskal's Union-Find, tie handling of frequencies in a Huffman tree, the boundary (finish=start) condition of activity selection—can break optimality, so include verification of boundary cases such as unreachable, empty input, and equal weights in the design.
Actively leverage the combination of greedy with other paradigms. Greedy is useful not only standalone but also as a means of accelerating or initializing other techniques. Branch and bound prunes brute force with a greedy upper bound, local search and metaheuristics improve by taking the greedy solution as an initial solution, and extension theories like matroid intersection broaden greedy's scope of application. This integrated perspective of viewing greedy as one component of the overall optimization design enhances practical problem-solving power.
In summary, a greedy algorithm is the simple strategy of "grab the best at each moment and never look back," but its legitimacy is underpinned by the greedy choice property and optimal substructure, and further by the deep structure of matroids. When conditions hold, greedy provides provably optimal solutions in polynomial time—like minimum spanning tree, Huffman coding, and activity selection—and for hard problems it offers practical solutions with a guaranteed approximation ratio. A professional engineer must possess the competence to accurately diagnose the problem's structure, choose the right paradigm among greedy, dynamic programming, and brute force, argue legitimacy, and combine techniques at the balance point of correctness and performance.
References
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to Algorithms" (3rd/4th ed.), Chapter 16: Greedy Algorithms, MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE, 1952. https://ieeexplore.ieee.org/document/4051119
- J. Edmonds, "Matroids and the greedy algorithm", Mathematical Programming, 1971. https://link.springer.com/article/10.1007/BF01584082
- V. Chvátal, "A Greedy Heuristic for the Set-Covering Problem", Mathematics of Operations Research, 1979. https://pubsonline.informs.org/doi/10.1287/moor.4.3.233
In one line: A greedy algorithm is the strategy of choosing the local optimum at each step and never revoking it; when the greedy choice property and optimal substructure (and further, a matroid) hold, it guarantees optimal solutions in polynomial time—like minimum spanning tree, Huffman coding, and fractional knapsack—but when the conditions break it produces a wrong answer, so the key is to verify legitimacy via the exchange argument and diagnose the boundary with dynamic programming and brute force to select the right paradigm.