cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 139 of 218
Ideas this builds on
Greedy choices139 / 218

A plausible local rule is a hypothesis

Picture

A greedy algorithm commits to a choice using a local rule and continues without exploring alternatives to that commitment. That can be efficient, but “looks best now” is only a hypothesis. Before trusting it, try to make the choice damage a better future arrangement.

Predict

Unlimited coin denominations are [1, 3, 4], target 6. Does repeatedly taking the largest coin that fits minimize the number of coins?

Reveal the reasoning

No. Greedy takes 4+1+1, three coins. 3+3 uses two. One counterexample disproves the general rule even if it worked on many earlier inputs.

Go deeper: attack the claimed guarantee
def largest_first(coins, target):
    used = 0
    for coin in sorted(coins, reverse=True):
        count, target = divmod(target, coin)
        used += count
    return used if target == 0 else -1

assert largest_first([1, 3, 4], 6) == 3  # Demonstrates the bad rule.
assert 3 + 3 == 6                      # A better two-coin construction.

The sample rule costs O(m log m) for m positive denominations, but fast execution does not imply correctness. Coin-system restrictions can make largest-first valid; that requires a property of that system, not of all coin problems.

For single-use knapsack, a value-per-weight ratio is also only a hypothesis. With capacity 50 and items (10,60), (20,100), (30,120), ratio-first selects the first two for 160, while the last two give 220. If fractions of items are allowed instead, ratio-first has a different feasibility structure and a valid exchange argument.

To search for counterexamples, use tiny competing choices: one locally attractive choice that blocks two moderately attractive choices, or one cheap step leading to an expensive remainder. Small examples expose the exact assumption that fails.

If a greedy rule fails, do not immediately conclude “therefore DP.” A different greedy rule may work, or the problem may need another structure or a more expensive search. Return to the state and constraints.

Analogy limit: greedy is not defined by sorting. Sorting can support DP, search, or preprocessing too. What matters is the commitment and its justification.

Change one rule

Every coin denomination is a power of two, including 1. What supports taking the largest fitting coin now?

Check the variation

Two coins of any smaller denomination can be replaced by one coin of the next denomination, reducing count without changing value. Repeated exchanges lead to the binary representation chosen by largest-first. The denomination structure supplies the missing proof.

Connect

Interval scheduling develops a full exchange proof. Weighted intervals changes its objective and breaks the rule. Dijkstra commits using a nonnegative-cost guarantee.