算法专题：贪心算法 (Greedy Algorithm)
相关数据结构实现用go语言实现
相关代码做题合集：https://github.com/longpi1/algorithm-pattern
1. 引言
在计算机科学中，贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。它不从整体最优上加以考虑，而是只关注局部最优解。
简单来说，贪心算法就像一个“鼠目寸光”的决策者：它只看眼前的利益，做出当下看起来最划算的选择，并希望通过一系列这样的局部最优选择，最终能达到一个全局最优解。
2. 核心思想与基本原理
贪心算法的核心思想可以用两个字概括：“局部最优推导出全局最优”。
它在每一步做出选择时，都会遵循以下原则：
- **做出当下看起来最优的选择 (Greedy Choice)**：不考虑未来的后果，只选择当前状态下能带来最大收益或最小成本的选项。
- **不回溯 (No Backtracking)**：一旦做出选择，就永远不会改变。这是贪心算法与动态规划（通常会考虑所有子问题，并可能回溯）的最大区别。
3. 贪心算法的特性
一个问题能够用贪心算法解决，通常需要满足以下两个关键性质：
3.1 贪心选择性质 (Greedy Choice Property)
- 定义：一个全局最优解可以通过一系列局部最优（贪心）选择来达到。这意味着每一步的局部最优选择，最终都会成为全局最优解的一部分。
- 重要性：这是贪心算法能够成功的核心前提。如果一个问题的最优解不能通过贪心选择来构建，那么贪心算法就不适用。
3.2 最优子结构性质 (Optimal Substructure)
- 定义：一个问题的最优解包含其子问题的最优解。
- 重要性：这个性质与动态规划所要求的性质相同。它表示问题的规模可以通过最优选择不断缩小，并且缩小后的子问题仍然具有最优解。
注意：证明一个贪心算法的正确性是至关重要的，通常采用反证法或归纳法。因为“局部最优不一定能推导出全局最优”是贪心算法最常见的陷阱。
4. 贪心算法的适用场景
贪心算法通常用于解决优化问题，即在给定约束条件下找到最大或最小的某个值。它广泛应用于以下领域：
- 调度问题：如活动选择问题、任务调度。
- 图算法：如最小生成树（Prim算法、Kruskal算法）、最短路径（Dijkstra算法）。
- 背包问题：分数背包问题（0/1背包问题通常不能用贪心）。
- 货币找零问题（在标准币值下）。
5. 贪心算法的局限性
贪心算法的最大局限性在于其“短视”。它只关注当前局部最优，不考虑未来的影响，这可能导致最终结果并非全局最优。
经典反例：
- 非标准币值下的找零问题：假设我们有币值
[1, 3, 4]，要找零 6。
- 贪心策略：总是选择面值最大的硬币。
- 过程：选择
4，剩余 2。再选择 1，剩余 1。再选择 1，剩余 0。总共使用了 3 枚硬币 (4, 1, 1)。
- 最优解：选择
3，剩余 3。再选择 3，剩余 0。总共使用了 2 枚硬币 (3, 3)。
- 结论：贪心算法在这里失败了。
- 0/1 背包问题：物品不能被分割。
- 贪心策略：按价值密度（价值/重量）排序，优先选择价值密度高的。
- 反例：背包容量10。物品A(价值60, 重量10, 密度6)，物品B(价值100, 重量20, 密度5)，物品C(价值120, 重量30, 密度4)。
- 贪心会选择A (价值60)，然后背包满了。总价值60。
- 最优解：B和C都不能单独装。但如果物品可以被分割，则贪心有效（见下文分数背包）。对于0/1背包，这是动态规划的经典问题。
6. 贪心算法与其它算法范式的区别
- **与动态规划 (Dynamic Programming)**：
- 相似点：都利用最优子结构性质。
- 不同点：
- 选择方式：贪心每一步只做一个最优选择，不回头。动态规划会尝试所有可能的子问题，并存储中间结果，从子问题的最优解构建原问题的最优解。
- 适用范围：贪心适用范围更窄，要求具有贪心选择性质。动态规划适用范围更广，只要有重叠子问题和最优子结构即可。
- 效率：贪心算法通常比动态规划更简单、更高效（时间复杂度更低），因为它无需考虑所有可能，但前提是它能给出正确解。
- **与分治法 (Divide and Conquer)**：
- 相似点：都将问题分解为子问题。
- 不同点：
- 子问题关系：分治法的子问题是独立的，互不影响。贪心算法的每一步选择会影响到后续子问题的输入。
- 合并：分治法需要将子问题的解合并，而贪心法通过一系列选择直接构建最终解。
7. 贪心算法的通用步骤
- 明确目标：确定要最大化或最小化的目标。
- 定义贪心选择：确定在每一步中要做出什么“局部最优”的选择。
- 证明正确性：这是最关键的，证明局部最优选择能够导出全局最优解。这通常是最难的部分。
- 实现：根据定义的贪心策略编写代码。通常涉及排序和迭代。
8. Go 语言实现示例
示例1：活动选择问题 (Activity Selection Problem)
问题描述：假设有一个教室，可以进行多项活动。每项活动都有开始时间 s 和结束时间 f。你的目标是选择尽可能多的活动，使得这些活动都可以在这个教室进行，即它们的时间互不重叠。
贪心策略：总是选择结束时间最早的活动。
证明（直观）：选择结束时间最早的活动，可以尽快地释放教室，为后续的活动留下最大的时间空间，从而使得能安排的活动数量最多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| package main
import (
"fmt"
"sort"
)
type Activity struct {
Start int
End int
}
type ByEndTime []Activity
func (a ByEndTime) Len() int { return len(a) }
func (a ByEndTime) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByEndTime) Less(i, j int) bool { return a[i].End < a[j].End }
func activitySelection(activities []Activity) []Activity {
if len(activities) == 0 {
return nil
}
sort.Sort(ByEndTime(activities))
selectedActivities := []Activity{activities[0]}
lastFinishTime := activities[0].End
for i := 1; i < len(activities); i++ {
if activities[i].Start >= lastFinishTime {
selectedActivities = append(selectedActivities, activities[i])
lastFinishTime = activities[i].End
}
}
return selectedActivities
}
func main() {
activities := []Activity{
{Start: 1, End: 4},
{Start: 3, End: 5},
{Start: 0, End: 6},
{Start: 5, End: 7},
{Start: 3, End: 8},
{Start: 5, End: 9},
{Start: 6, End: 10},
{Start: 8, End: 11},
{Start: 8, End: 12},
{Start: 2, End: 13},
{Start: 12, End: 14},
}
fmt.Println("原始活动列表:")
for _, a := range activities {
fmt.Printf(" [%d, %d]\n", a.Start, a.End)
}
selected := activitySelection(activities)
fmt.Println("\n选择的活动 (贪心算法):")
for _, a := range selected {
fmt.Printf(" [%d, %d]\n", a.Start, a.End)
}
}
|
示例2：货币找零问题 (Coin Change Problem) - 贪心失效的例子
问题描述：给定一些不同面额的硬币 denominations 和一个总金额 amount，找出凑成该金额所需的最少硬币数量。
贪心策略：总是选择当前剩余金额下能用的最大面额硬币。
证明（标准币值）：对于像 [1, 5, 10, 25] 这样的标准美元或人民币币值，这个贪心策略是有效的。这是因为大面额硬币的价值与小面额硬币之间存在特殊的倍数关系，使得局部最优推导全局最优。
反例演示：然而，如果币值不标准，贪心策略就会失效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| package main
import (
"fmt"
"sort"
)
func coinChangeGreedy(denominations []int, amount int) int {
if amount < 0 {
return -1
}
if amount == 0 {
return 0
}
sort.Sort(sort.Reverse(sort.IntSlice(denominations)))
count := 0
remainingAmount := amount
for _, coin := range denominations {
for remainingAmount >= coin {
remainingAmount -= coin
count++
fmt.Printf(" 选择硬币 %d, 剩余金额 %d, 硬币数量 %d\n", coin, remainingAmount, count)
}
if remainingAmount == 0 {
break
}
}
if remainingAmount == 0 {
return count
} else {
return -1
}
}
func main() {
denominations1 := []int{1, 5, 10, 25}
amount1 := 63
fmt.Printf("--- 标准币值找零 (贪心有效) ---\n")
fmt.Printf("面额: %v, 金额: %d\n", denominations1, amount1)
result1 := coinChangeGreedy(denominations1, amount1)
fmt.Printf("所需最少硬币数量 (贪心): %d\n", result1)
fmt.Println("\n--- 非标准币值找零 (贪心失效) ---")
denominations2 := []int{1, 3, 4}
amount2 := 6
fmt.Printf("面额: %v, 金额: %d\n", denominations2, amount2)
result2 := coinChangeGreedy(denominations2, amount2)
fmt.Printf("所需最少硬币数量 (贪心): %d\n", result2)
}
|
示例3：分数背包问题 (Fractional Knapsack Problem)
问题描述：你有一个背包，最大载重为 capacity。有 N 件物品，每件物品有其价值 value 和重量 weight。你可以选择拿走物品的一部分。目标是最大化你带走物品的总价值。
贪心策略：总是优先选择单位重量价值最高的物品（即价值/重量 比值最大的物品）。
证明（直观）：如果你能分割物品，那么单位重量价值高的物品意味着你在有限的重量限制下，能获得更多的价值。优先填满这些“高密度”价值的物品，将最大化总价值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| package main
import (
"fmt"
"sort"
)
type Item struct {
Value float64
Weight float64
Ratio float64
}
type ByRatio []Item
func (a ByRatio) Len() int { return len(a) }
func (a ByRatio) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByRatio) Less(i, j int) bool {
return a[i].Ratio > a[j].Ratio
}
func fractionalKnapsack(items []Item, capacity float64) float64 {
if capacity <= 0 || len(items) == 0 {
return 0
}
for i := range items {
if items[i].Weight > 0 {
items[i].Ratio = items[i].Value / items[i].Weight
} else {
items[i].Ratio = 0
}
}
sort.Sort(ByRatio(items))
totalValue := 0.0
currentWeight := 0.0
for _, item := range items {
if currentWeight+item.Weight <= capacity {
totalValue += item.Value
currentWeight += item.Weight
fmt.Printf(" 装入整个物品: 价值 %.2f, 重量 %.2f. 当前总价值: %.2f, 剩余容量: %.2f\n",
item.Value, item.Weight, totalValue, capacity-currentWeight)
} else {
remainingCapacity := capacity - currentWeight
fraction := remainingCapacity / item.Weight
totalValue += item.Value * fraction
currentWeight += remainingCapacity
fmt.Printf(" 装入部分物品: 价值 %.2f, 重量 %.2f (占比 %.2f). 当前总价值: %.2f, 剩余容量: %.2f\n",
item.Value*fraction, remainingCapacity, fraction, capacity-currentWeight)
break
}
}
return totalValue
}
func main() {
items := []Item{
{Value: 60, Weight: 10},
{Value: 100, Weight: 20},
{Value: 120, Weight: 30},
}
capacity := 50.0
fmt.Println("--- 分数背包问题 ---")
fmt.Printf("背包容量: %.2f\n", capacity)
fmt.Println("物品列表:")
for _, item := range items {
fmt.Printf(" 价值: %.2f, 重量: %.2f\n", item.Value, item.Weight)
}
maxValue := fractionalKnapsack(items, capacity)
fmt.Printf("\n背包中可获得的最大价值: %.2f\n", maxValue)
}
|
9. 结论
贪心算法是一种简单直观、高效的算法设计策略，但它的适用性相对有限。成功的贪心算法通常需要严格的数学证明来保证其局部最优选择能够导出全局最优解。在面对一个新问题时，首先尝试设计贪心策略，然后尝试证明或寻找反例，如果贪心不奏效，再考虑动态规划等更通用的方法。
