已发布·持续改进
贪心算法 指南 · 1/6
本章目前仅提供英文版。
A greedy algorithm builds a solution through a sequence of choices, and at each step it takes whatever looks best right now, never revisiting that decision. Unlike exhaustive search, which tries every option, or dynamic programming, which tabulates answers to subproblems, a greedy algorithm follows a single path. That makes it short and fast, but you have to prove separately that the path actually leads to an optimal answer.
| Term | Meaning |
|---|---|
| Greedy choice | Picking the candidate that is best by a fixed rule in the current state |
| Greedy choice property | Some optimal solution always contains the first greedy choice |
| Optimal substructure | After the first choice, an optimal answer to the remaining problem completes an optimal answer overall |
| Exchange argument | A proof that swaps parts of an optimal solution toward the greedy one without making it worse |
| Greedy stays ahead | A proof that after every step the greedy solution is at least as good as any other |
A greedy algorithm is correct when the greedy choice property and optimal substructure both hold. The first guarantees that the first choice is never a mistake; the second guarantees that the rest of the problem can be solved the same way. Together they give an inductive proof that every choice is safe.
The exchange argument is the workhorse of greedy proofs, and it almost always has the same shape.
Take the problem of choosing as many non-overlapping meetings as possible, where greedy picks the meeting that finishes first. Replace the first meeting of any optimal schedule with the earliest-finishing one: the new meeting ends no later than the old one, so it cannot collide with anything that followed. The count is unchanged, so the swap costs nothing.
Paying out change with the largest coins first is the most familiar greedy algorithm. In a well-designed coin system such as US coins (1, 5, 10, 25 cents) it always uses the fewest coins.
def greedy_coins(coins, amount):
"""Use as many large coins as possible. None if the amount cannot be made."""
count = 0
for coin in sorted(coins, reverse=True):
take, amount = divmod(amount, coin)
count += take
return count if amount == 0 else None
print(greedy_coins([1, 5, 10, 25], 63)) # 6 (25 * 2 + 10 + 1 * 3)Now suppose the coins are 1, 3 and 4 and you owe 6. Greedy grabs a 4 and then two 1s, three coins in total. Two 3s would do with only two coins. The first greedy choice (the 4) is not part of any optimal answer, so the greedy choice property is broken. Here you need dynamic programming, which computes the minimum for every amount.
def min_coins(coins, amount):
"""Dynamic programming: best[a] = fewest coins that make a."""
INF = float("inf")
best = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1
return best[amount] if best[amount] != INF else None
print(greedy_coins([1, 3, 4], 6), min_coins([1, 3, 4], 6)) # 3 2Before you write a proof, or whenever you doubt one, the quickest check is to compare the greedy answer with a known-correct one (brute force or dynamic programming) on small inputs. A single counterexample is enough to reject a greedy rule.
def find_counterexample(coins, limit=100):
for amount in range(1, limit + 1):
g, d = greedy_coins(coins, amount), min_coins(coins, amount)
if g != d:
return amount, g, d
return None
print(find_counterexample([1, 3, 4])) # (6, 3, 2)
print(find_counterexample([1, 5, 10, 25])) # NoneFinding no counterexample is not a proof, but it is very effective at discarding wrong rules early.
0 条评论
登录 · 登录后即可发表评论。
来发表第一条评论吧。