45:"/_next/static/chunks/33yus346z0l_n.js" 46:"/_next/static/chunks/2j22cxchii_xx.js" 47:"/_next/static/chunks/0iv56yrji_20j.js" 48:"/_next/static/chunks/32izpn90gvm22.js" 49:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4a:"/_next/static/chunks/1z-pox7hqp2x3.js" 4b:"/_next/static/chunks/20w4eaqlekefm.js" 4c:"/_next/static/chunks/1tn-0fivsxsv1.js" 4d:"/_next/static/chunks/09nq57stwzkgf.js" 4e:"/_next/static/chunks/3m1xjj5kw5fie.js" 4f:"/_next/static/chunks/0gafyzg9j9yqj.js" 50:"/_next/static/chunks/3k2gyg36fnag_.js" 51:"/_next/static/chunks/3bgoyiso1rhn7.js" 52:"/_next/static/chunks/3cstd6xzfli_o.js" 53:"/_next/static/chunks/253gnmj0-cj17.js" 54:"/_next/static/chunks/0hlb44ca7-4a2.js" 55:"/_next/static/chunks/20329i6m_04t6.js" 56:"/_next/static/chunks/40mq7ggq-ozo4.js" 57:"/_next/static/chunks/082jo-0ajazgr.js" 58:"/_next/static/chunks/2ozcrjb_hh74t.js" 59:"/_next/static/chunks/01a-3hvnqu8wl.js" 5a:"/_next/static/chunks/05i8en-x14ibi.js" 5b:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5c:"/_next/static/chunks/2k8pepwc4pxns.js" 5d:"/_next/static/chunks/0wa9m1-tphf9u.js" 5e:"/_next/static/chunks/30jdm3dwz834g.js" 5f:"/_next/static/chunks/0k9bl6dipnsvu.js" 60:"/_next/static/chunks/18ggtgz2yf759.js" 61:"/_next/static/chunks/0i3-eynrkvqi7.js" 62:I[593304,["$2a","$2b","$2c","$2d","$2e","$2f","$45","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61"],"OwnedHydration"] 63:T6ee,# Trace the remaining problem after each greedy choice activities = [ ("A1", 1, 4), ("A2", 3, 5), ("A3", 0, 6), ("A4", 5, 7), ("A5", 3, 9), ("A6", 5, 9), ("A7", 6, 10), ("A8", 8, 11), ("A9", 8, 12), ("A10", 2, 14), ("A11", 12, 16) ] def analyze_remaining_problem(selected, activities, step): """Analyze the remaining problem after greedy choice.""" print(f" {'='*60}") print(f"STEP {step}: After selecting {selected}") print(f"{'='*60}") if selected: last_finish = max(a[2] for a in selected) remaining = [(name, s, f) for name, s, f in activities if (name, s, f) not in selected and s >= last_finish] else: remaining = activities[:] print(f" Remaining Problem P_{step}:") print(f" Number of activities: {len(remaining)} (was {len(activities)})") print(f" Available activities: {[a[0] for a in remaining]}") if remaining: min_finish = min(a[2] for a in remaining) greedy_choice = [a for a in remaining if a[2] == min_finish][0] print(f" Next greedy choice (earliest finish): {greedy_choice[0]} " f"(finish={greedy_choice[2]})") print(f" Constraint modification:") print(f" Original: 'start_time >= 0'") print(f" Modified: 'start_time >= {last_finish if selected else 0}'") return remaining # Trace through the algorithm selected = [] remaining = activities[:] for step in range(4): # First 4 steps remaining = analyze_remaining_problem(selected, activities, step) if remaining: # Make greedy choice min_finish = min(a[2] for a in remaining) choice = [a for a in remaining if a[2] == min_finish][0] selected.append(choice)64:T9ff,// Formal model of greedy state transitions interface GreedyState { remaining: Set; // R: available elements constraints: Constraint; // C: current constraint state accumulated: number; // v: value so far } interface Constraint { // Abstract constraint representation isSatisfied(element: any): boolean; afterChoice(element: any): Constraint; } class GreedyStateMachine { private selectionCriterion: (remaining: Set) => Element; private valueFunction: (element: Element) => number; private incompatibilityTest: (e: Element, chosen: Element, c: Constraint) => boolean; constructor( criterion: (remaining: Set) => Element, value: (element: Element) => number, incompatible: (e: Element, chosen: Element, c: Constraint) => boolean ) { this.selectionCriterion = criterion; this.valueFunction = value; this.incompatibilityTest = incompatible; } /** * The state transition function T(σ, x) * This is the formal model of "what remains after greedy choice" */ transition(state: GreedyState, choice: Element): GreedyState { const newRemaining = new Set(); for (const element of state.remaining) { // Element survives if: // 1. It's not the chosen element // 2. It's compatible with the choice under current constraints if (element !== choice && !this.incompatibilityTest(element, choice, state.constraints)) { newRemaining.add(element); } } return { remaining: newRemaining, constraints: state.constraints.afterChoice(choice), accumulated: state.accumulated + this.valueFunction(choice), }; } /** * Execute full greedy algorithm, returning all intermediate states */ execute(initial: GreedyState): { states: GreedyState[]; choices: Element[]; } { const states: GreedyState[] = [initial]; const choices: Element[] = []; let current = initial; while (current.remaining.size > 0) { const choice = this.selectionCriterion(current.remaining); choices.push(choice); current = this.transition(current, choice); states.push(current); } return { states, choices }; } }65:T40a,def huffman_reduction_analysis(symbols): """ Tree-building reduction pattern. Each step combines two elements into one. """ import heapq # Create min-heap of (frequency, symbol_or_subtree) heap = [(freq, sym) for sym, freq in symbols.items()] heapq.heapify(heap) step = 0 while len(heap) > 1: step += 1 # Extract two minimum freq1, node1 = heapq.heappop(heap) freq2, node2 = heapq.heappop(heap) # Create combined node combined_freq = freq1 + freq2 combined_node = (node1, node2) print(f"Step {step}: Combine {node1}({freq1}) + {node2}({freq2})") print(f" Remaining problem: {len(heap)} nodes + 1 new") print(f" New node frequency: {combined_freq}") # Insert back - problem is now SMALLER but SAME TYPE heapq.heappush(heap, (combined_freq, combined_node)) print(f" Heap size: {len(heap)} (was {len(heap)+1})") return heap[0]66:T425,def interval_covering_reduction(target_start, target_end, intervals): """ Covering reduction pattern. Each choice reduces what remains to be covered. """ current_pos = target_start selected = [] while current_pos < target_end: # Find interval starting <= current_pos with maximum reach best = None best_reach = current_pos for start, end in intervals: if start <= current_pos and end > best_reach: best = (start, end) best_reach = end if best is None: return None # Impossible to cover selected.append(best) # REDUCTION: Update what remains to be covered old_pos = current_pos current_pos = best_reach print(f"Selected {best}, advanced from {old_pos} to {current_pos}") print(f"Remaining to cover: [{current_pos}, {target_end}]") # Problem is SAME TYPE: "cover remaining interval with available intervals" return selected43:["$","$L62",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792309778760,"state":{"data":{"json":{"id":"seed_420bdb67a9a226c517ab012a41abeed6","slug":"optimal-substructure-for-greedy","category":"Data Structures & Algorithms","topic":"Optimal Substructure for Greedy","title":"Optimal Substructure for Greedy Algorithms","description":"Master the concept of optimal substructure in greedy algorithms. Understand how greedy choices create smaller subproblems, the connection to divide-and-conquer and dynamic programming, and why this structural property is essential for greedy correctness.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_76eed070e78f871cc60b92da873d6798","title":"Remaining Problem After Greedy Choice","order":0,"content":[{"id":"opening-hook","title":"The Anatomy of a Greedy Decision","content":[{"data":{"content":"Every greedy algorithm follows a deceptively simple pattern: make a choice, then solve what remains. But beneath this simplicity lies a profound structural transformation. When a greedy algorithm makes its \"best local choice,\" it doesn't just move forward—it **fundamentally reshapes the problem landscape**.\n\nUnderstanding this transformation is crucial. The remaining problem after a greedy choice isn't arbitrary; it has specific properties that determine whether the greedy approach will succeed or fail. This page dissects the anatomy of post-choice problem states, revealing the hidden structure that makes greedy algorithms work."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand exactly what happens to a problem after a greedy choice is made. You'll learn to analyze the \"remaining problem\" structure, recognize when this structure supports greedy correctness, and identify warning signs that the remaining problem may not be well-behaved for greedy approaches.","variant":"info"},"type":"callout"}]},{"id":"greedy-decomposition","title":"The Greedy Decomposition Model","content":[{"data":{"content":"To understand what remains after a greedy choice, we must first formalize how greedy algorithms decompose problems. Unlike divide-and-conquer, which splits problems into multiple independent subproblems, or dynamic programming, which considers all subproblems simultaneously, greedy algorithms follow a **sequential decomposition** model.\n\n**The Formal Model:**\n\nLet P be an optimization problem. A greedy algorithm operates as follows:\n\n1. **Choose**: Select element x from the available choices in P\n2. **Commit**: Add x to the solution being constructed\n3. **Transform**: Derive the remaining problem P' from P, given that x is in the solution\n4. **Repeat**: Apply the same process to P' until no choices remain\n\nThe critical insight is in step 3: the transformation from P to P'. This isn't merely \"P minus x\"—it's often a fundamentally different problem with modified constraints, reduced options, and altered objective functions."},"type":"text"},{"data":{"icon":"Info","title":"Sequential vs Parallel Decomposition","content":"In divide-and-conquer, we split a problem into subproblems that can (conceptually) be solved in parallel—they don't depend on each other's solutions. In greedy algorithms, decomposition is inherently sequential: each subproblem depends on the choices made before it. This sequential dependency is both the strength (simplicity) and weakness (potential for globally suboptimal solutions) of greedy approaches.","variant":"note"},"type":"callout"},{"data":{"content":"**Visualizing the Transformation:**\n\nConsider how different problems transform after a greedy choice:\n\n1. **Activity Selection**: After selecting activity A that ends earliest, the remaining problem is *all activities that start after A ends*. The transformation eliminates conflicting activities and shifts the \"legal start time\" forward.\n\n2. **Fractional Knapsack**: After taking as much as possible of the item with highest value/weight ratio, the remaining problem has *reduced capacity* and *fewer items* (or reduced quantity of one item).\n\n3. **Huffman Coding**: After combining the two lowest-frequency symbols into a new super-symbol, the remaining problem has *one fewer symbol* but *modified frequencies*.\n\nEach transformation fundamentally alters the problem structure while preserving the essential nature of the optimization goal."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"characterizing-remaining","title":"Characterizing the Remaining Problem","content":[{"data":{"content":"The remaining problem P' after a greedy choice has several key characteristics that we must analyze to understand greedy correctness. Let's formalize these characteristics:"},"type":"text"},{"data":{"items":["**Size Reduction** — The remaining problem P' should be strictly smaller than P in some measurable way. This could be fewer elements, reduced capacity, smaller input size, or decreased resource availability. Without guaranteed size reduction, termination isn't assured.","**Constraint Modification** — The constraints in P' may differ from P. After choosing activity A, constraints shift from \"activities that don't conflict with anything\" to \"activities that don't conflict with A.\" Understanding constraint modification reveals which options remain viable.","**Objective Preservation** — The objective function in P' should relate meaningfully to P's objective. Typically, if we've already accumulated value V from our greedy choice, P' optimizes the same objective with V already \"banked.\"","**Independence** — Crucially, the optimal solution to P' should be optimal regardless of how we got there. The history of choices should be summarized entirely in the current state—no hidden dependencies on past decisions.","**Type Preservation** — For greedy to work recursively, P' should be \"the same kind of problem\" as P. An activity selection problem should remain an activity selection problem; a knapsack should remain a knapsack."],"title":{"icon":"Target","text":"Five Dimensions of Remaining Problem Analysis","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Formal Definition:**\n\nLet P = (S, C, f) be an optimization problem where:\n- S = set of possible solutions\n- C = constraints that valid solutions must satisfy\n- f = objective function to optimize\n\nAfter greedy choice x, the remaining problem P' = (S', C', f') where:\n- S' = solutions that extend {x} to complete solutions of P\n- C' = constraints from C, modified to account for x's inclusion\n- f' = objective measuring contribution beyond x's value\n\nThe greedy approach works when the optimal solution to P' combined with x yields an optimal solution to P."},"type":"text"},{"data":{"icon":"AlertCircle","title":"When Type Preservation Fails","content":"Some problems appear greedy-friendly but aren't because the remaining problem changes nature. In the 0/1 knapsack problem, after including an item, the remaining problem has modified capacity—but whether this changes the optimal strategy depends on the specific items remaining. This is why 0/1 knapsack requires dynamic programming: the remaining problem's optimal solution depends on which specific items we chose, not just their total weight.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"concrete-example","title":"Deep Dive: Activity Selection Remaining Problems","content":[{"data":{"content":"Let's trace through the activity selection problem in precise detail to see exactly how the remaining problem transforms at each step.\n\n**Initial Problem P₀:**\n- Activities: A₁(1,4), A₂(3,5), A₃(0,6), A₄(5,7), A₅(3,9), A₆(5,9), A₇(6,10), A₈(8,11), A₉(8,12), A₁₀(2,14), A₁₁(12,16)\n- Format: Activity(start_time, finish_time)\n- Objective: Maximize number of non-overlapping activities\n- Constraints: Selected activities must not overlap"},"type":"text"},{"data":{"code":"$63","fileName":"activity_selection_trace.py","showLineNumbers":true},"type":"code"},{"data":{"rows":[["0 → 1","A₁ (finish=4)","11 → 3","start ≥ 4","A₂, A₃, A₅, A₆, A₇, A₁₀ (overlap with A₁)"],["1 → 2","A₄ (finish=7)","3 → 2","start ≥ 7","A₇ (overlaps with A₄)"],["2 → 3","A₈ (finish=11)","2 → 1","start ≥ 11","A₉ (overlaps with A₈)"],["3 → 4","A₁₁ (finish=16)","1 → 0","start ≥ 16","None remaining"]],"caption":"Problem Transformation at Each Step","headers":["Step","Choice Made","|Remaining|","Effective Constraint","Eliminated Activities"]},"type":"table"},{"data":{"content":"**Key Observations:**\n\n1. **Monotonic constraint tightening**: The \"start ≥ t\" constraint only increases, never decreases. This is crucial—it means we never need to reconsider previously eliminated activities.\n\n2. **Predictable problem reduction**: Each step eliminates at least one activity (the chosen one), guaranteeing termination. But often many more are eliminated due to overlap.\n\n3. **State summarization**: The entire history of choices is summarized by a single number: the latest finish time. We don't need to remember *which* activities we chose, only *when* our last commitment ends.\n\n4. **Type preservation**: At every step, we're solving the same kind of problem: \"maximize non-overlapping activities from those remaining.\" The problem nature never changes."},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"mathematical-formalization","title":"Mathematical Formalization of Problem Reduction","content":[{"data":{"content":"Let's formalize the remaining problem concept mathematically, which will help us reason precisely about greedy correctness.\n\n**Definition: Problem State**\n\nDefine the state of a greedy optimization problem as a tuple σ = (R, C, v) where:\n- R = remaining elements that can be chosen\n- C = current constraints (may depend on previous choices)\n- v = value accumulated so far\n\n**Definition: State Transition Function**\n\nThe greedy algorithm defines a transition function T: State × Element → State:\n\nT(σ, x) = T((R, C, v), x) = (R', C', v')\n\nwhere:\n- R' = R \\ {x} \\ {incompatible elements given x and C}\n- C' = constraints updated to reflect x's inclusion\n- v' = v + value(x)"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Markov Property of Greedy States","content":"A well-designed greedy problem exhibits a Markov property: the optimal continuation from state σ depends only on σ, not on how we arrived at σ. This is analogous to the principle of optimality in dynamic programming. If this property fails—if the optimal future depends on the specific path taken—then greedy will likely fail.","variant":"tip"},"type":"callout"},{"data":{"content":"**Theorem: Greedy Optimality Condition**\n\nA greedy algorithm produces an optimal solution if and only if for every reachable state σ = (R, C, v):\n\n1. **Greedy Choice Existence**: There exists some x* ∈ R such that x* is part of an optimal completion of σ (i.e., some optimal solution extending current choices includes x*).\n\n2. **Reducibility**: T(σ, x*) results in a smaller problem that also satisfies condition 1.\n\n3. **Termination**: Repeated application reaches a terminal state with R = ∅.\n\n**The Remaining Problem Perspective:**\n\nThis theorem directly speaks to the remaining problem. After making choice x*, the remaining problem (R', C', 0) must itself have an optimal greedy solution. The value v' is \"banked\" and doesn't affect future decisions—only (R', C') matters.\n\nThis is why the remaining problem being \"simpler\" is so important: we need the inductive hypothesis (greedy works on smaller problems) to hold for the proof to go through."},"type":"text"},{"data":{"code":"$64","fileName":"greedy_state_machine.ts","showLineNumbers":true},"type":"code"}],"titleType":"number","titleNumber":4},{"id":"reduction-patterns","title":"Common Problem Reduction Patterns","content":[{"data":{"content":"Different classes of greedy problems exhibit characteristic patterns in how the remaining problem is structured. Recognizing these patterns helps identify when greedy approaches will work."},"type":"text"},{"data":{"tabs":[{"id":"interval-pattern","label":"Interval Reduction","content":[{"data":{"content":"**Pattern: Interval/Range Problems**\n\nIn interval scheduling problems, the remaining problem is defined by a **boundary shift**:\n\n- **Original Problem**: Select from intervals in range [0, ∞)\n- **After Choice of interval [a, b]**: Select from intervals in range [b, ∞)\n\n**Key Properties:**\n\n1. The boundary only moves forward (monotonic)\n2. The problem \"shape\" is identical—just with different boundary\n3. State is fully characterized by a single number (boundary position)\n\n**Why This Works:**\n\nThe earliest-finish-time heuristic works because:\n- Choosing earliest finish maximizes the remaining range [b, ∞)\n- A larger remaining range can only have more (or equal) options\n- Therefore, earliest-finish-time never \"paints us into a corner\""},"type":"text"},{"data":{"code":"def interval_reduction(intervals, current_time):\n \"\"\"\n After choosing interval ending at current_time,\n the remaining problem is all intervals starting at/after current_time.\n \n This is a canonical 'boundary shift' reduction.\n \"\"\"\n remaining = []\n for start, end in intervals:\n if start >= current_time: # Shifted constraint\n remaining.append((start, end))\n \n # The remaining problem is IDENTICAL in form:\n # \"Find maximum non-overlapping intervals from 'remaining'\"\n # Only the input set has changed, not the problem type\n return remaining","showLineNumbers":true},"type":"code"}],"titleIcon":"Target"},{"id":"capacity-pattern","label":"Capacity Reduction","content":[{"data":{"content":"**Pattern: Capacity-Constrained Problems**\n\nIn problems like fractional knapsack, the remaining problem is defined by **capacity reduction**:\n\n- **Original Problem**: Fill capacity C with items maximizing value\n- **After taking amount w of item i**: Fill capacity (C - w) with remaining items\n\n**Key Properties:**\n\n1. Capacity only decreases (monotonic)\n2. Items may be partially consumed or fully consumed\n3. State is characterized by remaining capacity + remaining items\n\n**Why Greedy Works for Fractional (but not 0/1):**\n\nIn fractional knapsack:\n- We can always take the best value-per-weight item (greedily optimal)\n- After partial consumption, the problem is identical—just smaller\n\nIn 0/1 knapsack:\n- After including item i, remaining capacity is C - wᵢ\n- BUT: whether to include item j now depends on what OTHER items we included\n- The remaining problem structure depends on choice history, not just capacity"},"type":"text"},{"data":{"code":"def fractional_knapsack_reduction(items, capacity):\n \"\"\"\n Capacity reduction pattern.\n After each greedy choice, capacity decreases.\n \"\"\"\n # Sort by value-to-weight ratio (greedy criterion)\n sorted_items = sorted(items, key=lambda x: x.value/x.weight, reverse=True)\n \n remaining_capacity = capacity\n solution = []\n \n for item in sorted_items:\n if remaining_capacity == 0:\n break\n \n # Take as much as possible\n take_amount = min(item.weight, remaining_capacity)\n fraction = take_amount / item.weight\n \n solution.append((item, fraction))\n remaining_capacity -= take_amount # Capacity reduction\n \n # Remaining problem: same type, smaller capacity\n # The greedy property: best ratio is ALWAYS optimal to take first\n \n return solution","showLineNumbers":true},"type":"code"}],"titleIcon":"Target"},{"id":"tree-pattern","label":"Tree Building","content":[{"data":{"content":"**Pattern: Tree Construction Problems**\n\nIn Huffman coding, the remaining problem transforms through **element combination**:\n\n- **Original Problem**: Build optimal tree from n symbols\n- **After combining two lowest-frequency symbols**: Build optimal tree from (n-1) symbols\n\n**Key Properties:**\n\n1. Number of elements decreases by 1 each step\n2. Combined element has aggregate frequency\n3. Tree structure is built bottom-up\n\n**The Reduction:**\n\n- Original: symbols {a:5, b:9, c:12, d:13, e:16, f:45}\n- After combining (a,b): {(ab):14, c:12, d:13, e:16, f:45}\n- The \"(ab)\" super-symbol behaves like any other symbol\n- Problem remains: \"build optimal tree from these symbols\"\n\n**Why This Works:**\n\nCombining lowest-frequency symbols guarantees they become siblings at maximum depth. Since these are accessed least frequently, putting them deepest minimizes expected path length."},"type":"text"},{"data":{"code":"$65","showLineNumbers":true},"type":"code"}],"titleIcon":"Target"},{"id":"covering-pattern","label":"Covering Problems","content":[{"data":{"content":"**Pattern: Covering/Hitting Problems**\n\nIn set cover and interval covering, the remaining problem is defined by **requirement reduction**:\n\n- **Original Problem**: Cover all elements in universe U\n- **After selecting set S**: Cover all elements in (U - S)\n\n**Key Properties:**\n\n1. Universe size decreases or stays same\n2. Remaining sets may become \"smaller\" (elements already covered are irrelevant)\n3. Terminal condition: universe becomes empty\n\n**Example: Interval Covering**\n\n- Need to cover interval [0, 10]\n- Available intervals: [0,3], [2,6], [5,8], [7,10]\n- Greedy choice: interval reaching furthest from current position\n\nAfter choosing [0,3]:\n- Remaining to cover: [3, 10]\n- Same problem, smaller requirement\n\n**Caution:**\n\nGeneral set cover is NP-hard. Greedy achieves O(log n) approximation but not optimality. Interval covering works because intervals have geometric structure."},"type":"text"},{"data":{"code":"$66","showLineNumbers":true},"type":"code"}],"titleIcon":"Target"}]},"type":"tabs"}],"titleType":"number","titleNumber":5},{"id":"structure-failure","title":"When Remaining Problem Structure Fails","content":[{"data":{"content":"Understanding when greedy fails is as important as understanding when it succeeds. Failure often stems from pathological properties of the remaining problem."},"type":"text"},{"data":{"items":["**Path-Dependent Optimality** — If the optimal solution to the remaining problem depends on *which specific elements* were chosen (not just aggregate properties), greedy often fails. The 0/1 knapsack exhibits this: whether to include item j depends on which earlier items were included.","**Non-Monotonic Constraints** — If constraints can loosen after a choice, earlier decisions may become suboptimal. Good greedy problems have constraints that only tighten (time boundaries advance, capacity decreases).","**Value Interaction** — If the value of choosing x depends on other elements in the solution, greedy's local view misses global interactions. In clustering problems, an item's \"value\" depends on what cluster it joins.","**Reversibility Requirements** — If optimal solutions require \"undoing\" or reconsidering earlier choices, greedy cannot succeed. Greedy commits irrevocably.","**Problem Type Mutation** — If the remaining problem becomes a fundamentally different type of problem, the greedy heuristic may not apply. After some choices, the structure may shift from \"maximization\" to \"satisfiability\" or vice versa."],"title":{"icon":"XCircle","text":"Red Flags in Remaining Problem Structure","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**Case Study: Why Greedy Fails for 0/1 Knapsack**\n\nConsider: Capacity = 10, Items: [(weight=6, value=30), (weight=5, value=25), (weight=5, value=25)]\n\n**Greedy by value/weight ratio:**\n- Item 1: ratio = 5, weight = 6 → Take it (remaining capacity: 4)\n- Items 2,3: ratio = 5, weight = 5 → Can't fit either!\n- Greedy solution: value = 30\n\n**Optimal solution:**\n- Take items 2 and 3: weight = 10, value = 50\n\n**Why did greedy fail?**\n\nAfter choosing item 1, the remaining problem (capacity=4) has a *different optimal structure* than if we hadn't chosen it. The \"remaining problem\" after item 1 is: \"can we fit anything in 4 units?\" Answer: no. But the remaining problem after *not* choosing item 1 is: \"fill 10 units optimally\"—which has a good solution.\n\nThe critical flaw: the value of the remaining problem depends on *which* item we chose, not just how much capacity we used. With same capacity reduction (6 units) from a different item, outcomes differ."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Fundamental Greedy Failure Mode","content":"Greedy fails when early choices create remaining problems whose optimal solutions are not compatible with the globally optimal solution. In other words: greedy assumes that \"optimal now + optimal remainder = global optimal.\" When this equation breaks—when optimal remainder depends on the PATH to the current state, not just the current state—greedy collapses.","variant":"error"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"summary","title":"Summary: Anatomy of the Remaining Problem","content":[{"data":{"content":"We've dissected the structure of what remains after a greedy choice. This understanding is foundational for reasoning about greedy correctness."},"type":"text"},{"data":{"type":"ordered","items":["**Sequential Decomposition** — Greedy algorithms decompose problems sequentially: make choice, transform problem, repeat. Each step creates a new \"remaining problem.\"","**Five Dimensions** — Analyze remaining problems along five dimensions: size reduction, constraint modification, objective preservation, independence, and type preservation.","**State Summarization** — Well-behaved greedy problems have states that can be summarized compactly, independent of the path taken to reach them.","**Common Patterns** — Remaining problem structures follow patterns: interval/boundary shift, capacity reduction, tree construction, and covering/requirement reduction.","**Failure Modes** — Greedy fails when remaining problem optimality is path-dependent, constraints are non-monotonic, values interact, or reversibility is required.","**Markov Property** — Successful greedy problems exhibit a Markov property: optimal continuation depends only on current state, not history."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"CheckCircle","title":"Next Steps","content":"You now understand what happens to a problem after a greedy choice. The next page explores why the remaining problem being 'similar but smaller' is so crucial—diving into the self-similar structure that makes greedy recursion possible.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7}],"isLocked":false},{"id":"seed_2f3f6a39ff9ea93b72da9030005ee30b","title":"Subproblem is Similar but Smaller","order":1,"content":null,"isLocked":true},{"id":"seed_33e91553339d0e6413a5730b6abd7a69","title":"Connection to D&C and DP","order":2,"content":null,"isLocked":true},{"id":"seed_14c501a137f0f1d2c24f246d0512608b","title":"Why Optimal Substructure Matters","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792309778719,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"optimal-substructure-for-greedy"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"optimal-substructure-for-greedy\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309778760,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792309778718,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_420bdb67a9a226c517ab012a41abeed6"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_420bdb67a9a226c517ab012a41abeed6\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309778760,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792309778718,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_2f3f6a39ff9ea93b72da9030005ee30b"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_2f3f6a39ff9ea93b72da9030005ee30b\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309778760,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792309778718,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_2f3f6a39ff9ea93b72da9030005ee30b"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_2f3f6a39ff9ea93b72da9030005ee30b\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309778760,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792309778718,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_2f3f6a39ff9ea93b72da9030005ee30b"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_2f3f6a39ff9ea93b72da9030005ee30b\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792309778760,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_2f3f6a39ff9ea93b72da9030005ee30b","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_2f3f6a39ff9ea93b72da9030005ee30b\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@67"}]},"children":"$L68"}]