贪心算法入门指南（Go语言实现与最优子结构详解）

Go语言实战：活动选择问题

我们以经典的“活动选择问题”为例，来展示贪心算法如何利用最优子结构解决问题。

问题描述：有 n 个活动，每个活动有一个开始时间和结束时间。目标是从这些活动中选出尽可能多的活动，使得它们在时间上互不冲突。

贪心策略：每次选择结束时间最早的活动。这样可以为后续活动留下最多的时间空间。

这个策略之所以有效，是因为该问题具有最优子结构：假设我们选择了最早结束的活动 a₁，那么剩下的问题就是在 a₁ 结束之后的所有活动中再选最多的活动——这是一个规模更小的相同子问题。

Go语言代码实现

package mainimport (	"fmt"	"sort")// Activity 表示一个活动type Activity struct {	Start int	End   int}// ByEndTime 实现 sort.Interface，按结束时间排序type ByEndTime []Activityfunc (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 }// SelectActivities 使用贪心算法选择最多不冲突的活动func SelectActivities(activities []Activity) []Activity {	if len(activities) == 0 {		return []Activity{}	}	// 按结束时间升序排序	sorted := make([]Activity, len(activities))	copy(sorted, activities)	sort.Sort(ByEndTime(sorted))	result := []Activity{sorted[0]}	lastEnd := sorted[0].End	for i := 1; i < len(sorted); i++ {		if sorted[i].Start >= lastEnd {			result = append(result, sorted[i])			lastEnd = sorted[i].End		}	}	return result}func main() {	activities := []Activity{		{1, 4},		{3, 5},		{0, 6},		{5, 7},		{8, 9},		{5, 9},	}	selected := SelectActivities(activities)	fmt.Println("选中的活动（按结束时间排序）:")	for _, act := range selected {		fmt.Printf("[%d, %d]\n", act.Start, act.End)	}}

运行上述代码，你会看到输出：

选中的活动（按结束时间排序）:[1, 4][5, 7][8, 9]

这正是最大数量的不冲突活动组合。

为什么贪心在这里有效？

因为活动选择问题满足两个关键性质：

1. 贪心选择性质：局部最优（最早结束）能导向全局最优。
2. 最优子结构：原问题的最优解包含子问题的最优解。一旦选定第一个活动，剩下的就是在其结束后的新子问题。

总结

通过本教程，我们学习了Go语言中如何实现贪心算法，并深入理解了最优子结构在算法设计中的核心作用。记住：贪心算法虽简单高效，但仅适用于满足贪心选择性质和最优子结构的问题。常见的应用场景还包括找零钱（特定币值系统）、霍夫曼编码、最小生成树（Kruskal/Prim）等。

希望这篇算法教程能帮助你迈出掌握贪心算法的第一步！动手写一写代码，尝试修改活动数据，观察结果变化，加深理解。

关键词回顾：Go语言、贪心算法、最优子结构、算法教程