贪心算法
在 Go 语言中实现贪心算法时，和其他编程语言类似，核心思想是根据当前的局部最优选择来逐步构建全局最优解。下面是几个经典贪心算法的实现示例，以及如何在 Go 中编写这些算法。
1. 活动选择问题
活动选择问题的目标是选择尽可能多的互不重叠的活动。贪心策略是按活动的结束时间升序排序，然后每次选择第一个不与之前选择的活动重叠的活动。
示例代码：
go
package main
import "fmt"
// 定义活动结构体
type Activity struct {
start, end int
}
// 活动选择贪心算法
func activitySelection(activities []Activity) []Activity {
// 按照活动的结束时间排序
sort.Slice(activities, func(i, j int) bool {
return activities[i].end < activities[j].end
})
selectedActivities := []Activity{activities[0]} // 选择第一个活动
lastEndTime := activities[0].end
// 遍历剩余活动，选择不与前一个活动重叠的
for i := 1; i < len(activities); i++ {
if activities[i].start >= lastEndTime {
selectedActivities = append(selectedActivities, activities[i])
lastEndTime = activities[i].end
}
}
return selectedActivities
}
func main() {
activities := []Activity{
{1, 3}, {2, 5}, {4, 6}, {6, 8}, {5, 7},
}
selectedActivities := activitySelection(activities)
fmt.Println("Selected activities:")
for _, activity := range selectedActivities {
fmt.Printf("Start: %d, End: %d\n", activity.start, activity.end)
}
}2. 贪心算法求解找零问题
找零问题的目标是用尽可能少的硬币找零，贪心策略是每次选择面额最大的硬币，直到达到目标金额。
示例代码：
go
package main
import "fmt"
// 找零问题贪心算法
func coinChange(coins []int, amount int) []int {
// 按面额从大到小排序
sort.Sort(sort.Reverse(sort.IntSlice(coins)))
result := []int{}
for _, coin := range coins {
// 贪心选择尽可能多的最大面额硬币
for amount >= coin {
amount -= coin
result = append(result, coin)
}
}
return result
}
func main() {
coins := []int{1, 5, 10, 25}
amount := 63
result := coinChange(coins, amount)
fmt.Println("Coins used for change:", result)
}3. 最小生成树（MST）——普里姆算法
普里姆算法是用来求解无向加权图的最小生成树的贪心算法。在这个算法中，始终选择与当前树相连接的权重最小的边，直到所有节点都被包含在最小生成树中。
示例代码：
go
package main
import (
"fmt"
"math"
)
// 边的结构体
type Edge struct {
u, v, weight int
}
// 普里姆算法实现
func primMST(n int, graph [][]int) []Edge {
// 初始化
visited := make([]bool, n)
edges := []Edge{}
// 选择第一个节点
visited[0] = true
for len(edges) < n-1 {
minEdge := Edge{-1, -1, math.MaxInt32}
// 查找最小权重的边
for u := 0; u < n; u++ {
if visited[u] {
for v := 0; v < n; v++ {
if !visited[v] && graph[u][v] != 0 && graph[u][v] < minEdge.weight {
minEdge = Edge{u, v, graph[u][v]}
}
}
}
}
// 选择该边并标记新加入的节点
edges = append(edges, minEdge)
visited[minEdge.v] = true
}
return edges
}
func main() {
n := 5
graph := [][]int{
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},
}
mst := primMST(n, graph)
fmt.Println("Edges in the minimum spanning tree:")
for _, edge := range mst {
fmt.Printf("%d - %d with weight %d\n", edge.u, edge.v, edge.weight)
}
}4. 哈夫曼编码（Huffman Coding）
哈夫曼编码是一种无损压缩算法，它的贪心策略是每次选择出现频率最低的两个字符进行合并。
示例代码：
go
package main
import (
"fmt"
"container/heap"
)
// 定义哈夫曼树节点结构体
type HuffmanNode struct {
char rune
freq int
left *HuffmanNode
right *HuffmanNode
}
// 创建优先队列（最小堆）
type PriorityQueue []*HuffmanNode
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].freq < pq[j].freq
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(*HuffmanNode))
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
x := old[n-1]
*pq = old[0 : n-1]
return x
}
// 哈夫曼编码算法
func buildHuffmanTree(frequencies map[rune]int) *HuffmanNode {
pq := make(PriorityQueue, 0, len(frequencies))
for char, freq := range frequencies {
node := &HuffmanNode{char: char, freq: freq}
heap.Push(&pq, node)
}
for len(pq) > 1 {
// 从优先队列中取出两个最小的节点
left := heap.Pop(&pq).(*HuffmanNode)
right := heap.Pop(&pq).(*HuffmanNode)
// 合并它们生成一个新的节点
mergedNode := &HuffmanNode{
freq: left.freq + right.freq,
left: left,
right: right,
}
// 将新的节点插回优先队列
heap.Push(&pq, mergedNode)
}
// 返回最终的哈夫曼树根节点
return heap.Pop(&pq).(*HuffmanNode)
}
func main() {
// 输入字符及其频率
frequencies := map[rune]int{
'a': 5,
'b': 9,
'c': 12,
'd': 13,
'e': 16,
'f': 45,
}
// 构建哈夫曼树
root := buildHuffmanTree(frequencies)
// 输出哈夫曼树
fmt.Printf("Root of Huffman Tree: %+v\n", root)
}总结
这些示例展示了在 Go 中如何实现经典的贪心算法。贪心算法的关键在于选择当前阶段最优的解，并逐步构建最终的解。在实际应用中，要根据问题的具体要求判断是否可以使用贪心算法，确保问题具有“贪心选择性质”和“最优子结构”这两个特性。