Greedy algorithms
Đã giới thiệu
Từ vựng
| English | Ý nghĩa |
|---|---|
| greedy algorithm | greedy algorithm |
| exchange argument | exchange argument |
English
Take the best now
- A greedy algorithm builds the solution piece by piece, always taking the locally best piece. Correctness is a proof, not a hope: exchange arguments show any optimal solution can be transformed into the greedy one without loss.
{exercise:uni-cs1003-greedy}
Luyện tập
The exchange argument shows —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Swap optimal picks for greedy ones losslessly: same size, still feasible.
English
Activity selection, measured
- Course activities: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16). Earliest-finish picks (1,4), (5,7), (8,11), (12,16) — four, provably optimal.
- The exchange argument once: finish($G_1$) $\le$ finish($O_1$), so swapping the optimal's first pick for the greedy's keeps feasibility — repeat, and optimal becomes greedy, unchanged in size.
{exercise:uni-cs1003-activity}
Luyện tập
Earliest-finish on the course activities picks —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
(1,4), (5,7), (8,11), (12,16) - four, provably optimal.
English
Where greedy fails, and Huffman where it wins
- Coins 1, 3, 4, target 6: greedy pays 4+1+1 (three coins); the DP table pays 3+3 (two). The exchange argument fails, so greedy is a heuristic there.
- Huffman on frequencies 5, 9, 12, 13, 16, 45: repeatedly merge the two smallest — weighted depth 224 bits against 300 for a fixed-length code: provably minimal by the leaf-swap argument.
{exercise:uni-cs1003-huffman}
Luyện tập
Coins 1, 3, 4 for target 6: greedy pays — coins
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Greedy takes 4+1+1 = three coins; the DP optimum is 3+3 = two.