贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法解决问题的通用思路可以概括为以下几个步骤：

**建模：**将问题抽象成数学模型，明确问题的约束条件和优化目标。
**选择标准：**确定贪心策略，即如何在每一步做出局部最优选择。这通常涉及到对问题的深入理解和对可能解空间的分析。
**证明贪心策略的正确性：**通过数学归纳法或反证法等证明局部最优解能够导致全局最优解。
**实现算法：**根据贪心策略编写代码，实现算法的具体步骤。
**测试和验证：**通过测试案例验证算法的正确性和效率。

下面是一个使用 Go 语言实现的贪心算法的例子。这个例子是解决经典的硬币找零问题，即给定不同面额的硬币和一个总金额，要求用最少的硬币凑成总金额。

package main

import (
	"fmt"
	"sort"
)

func coinChange(coins []int, amount int) int {
	// 对硬币面额进行排序，从大到小
	sort.Slice(coins, func(i, j int) bool {
		return coins[i] > coins[j]
	})

	totalCoins := 0 // 使用的硬币数量
	for _, coin := range coins {
		// 使用当前面额的硬币数量
		count := amount / coin
		amount -= count * coin
		totalCoins += count

		// 如果已经凑够了总金额，直接返回结果
		if amount == 0 {
			return totalCoins
		}
	}

	// 如果不能凑够总金额，返回-1
	if amount > 0 {
		return -1
	}

	return totalCoins
}

func main() {
	coins := []int{1, 2, 5, 10, 20, 50}
	amount := 99
	fmt.Printf("Minimum coins needed: %d\n", coinChange(coins, amount))
}

在这个例子中，我们首先对硬币面额进行了排序，确保可以先使用大面额的硬币，这是贪心策略的一部分。然后，我们遍历每种硬币，尽可能多地使用当前面额的硬币，直到无法再使用该面额的硬币为止。如果最终能够凑齐总金额，则返回使用的硬币数量；如果不能，则返回-1。

需要注意的是，贪心算法并不总是能得到全局最优解，它的适用性依赖于问题本身的性质。在实际应用中，我们需要通过数学证明或经验判断来确定贪心策略是否适用于特定的问题。

以下是几个不同类型的贪心算法问题的 Go 语言实现例子：

例子 1：活动选择问题

假设你有一个活动列表，每个活动都有一个开始时间和结束时间。你的目标是选择最大数量的活动，使得它们不相互重叠。

package main

import (
	"fmt"
	"sort"
)

type Activity struct {
	Start, Finish int
}

// 按照活动结束时间排序
func activitySelection(activities []Activity) []Activity {
	sort.Slice(activities, func(i, j int) bool {
		return activities[i].Finish < activities[j].Finish
	})

	var result []Activity
	lastSelectedIndex := 0
	result = append(result, activities[lastSelectedIndex])

	for i := 1; i < len(activities); i++ {
		if activities[i].Start >= activities[lastSelectedIndex].Finish {
			result = append(result, activities[i])
			lastSelectedIndex = i
		}
	}

	return result
}

func main() {
	activities := []Activity{
		{Start: 1, Finish: 2},
		{Start: 3, Finish: 4},
		{Start: 0, Finish: 6},
		{Start: 5, Finish: 7},
		{Start: 8, Finish: 9},
		{Start: 5, Finish: 9},
	}

	selectedActivities := activitySelection(activities)
	for _, activity := range selectedActivities {
		fmt.Printf("Activity starts at: %d and finishes at: %d\n", activity.Start, activity.Finish)
	}
}

例子 2：分数背包问题

假设你是一个小偷，背着一个背包，背包有一个最大容量。你有一系列物品，每个物品都有重量和价值，你可以拿走物品的一部分。你的目标是在不超过背包容量的情况下，使得背包中物品的总价值最大。

package main

import (
	"fmt"
	"sort"
)

type Item struct {
	Weight, Value float64
}

// 按照单位价值排序
func fractionalKnapsack(items []Item, capacity float64) float64 {
	sort.Slice(items, func(i, j int) bool {
		return (items[i].Value / items[i].Weight) > (items[j].Value / items[j].Weight)
	})

	totalValue := 0.0
	for _, item := range items {
		if capacity > item.Weight {
			capacity -= item.Weight
			totalValue += item.Value
		} else {
			totalValue += item.Value * (capacity / item.Weight)
			break
		}
	}

	return totalValue
}

func main() {
	items := []Item{
		{Weight: 10, Value: 60},
		{Weight: 20, Value: 100},
		{Weight: 30, Value: 120},
	}
	capacity := 50.0

	maxValue := fractionalKnapsack(items, capacity)
	fmt.Printf("Maximum value we can obtain = %f\n", maxValue)
}

例子 3：最小的字典序

给定一个字符串，通过删除一些字符，使得剩下的字符串按字典序最小。

package main

import (
	"fmt"
)

func smallestSubsequence(s string) string {
	stack := []byte{}
	seen := make(map[byte]bool)
	lastOccurrence := make(map[byte]int)

	for i := range s {
		lastOccurrence[s[i]] = i
	}

	for i := range s {
		if seen[s[i]] {
			continue
		}

		for len(stack) > 0 && stack[len(stack)-1] > s[i] && lastOccurrence[stack[len(stack)-1]] > i {
			seen[stack[len(stack)-1]] = false
			stack = stack[:len(stack)-1]
		}

		stack = append(stack, s[i])
		seen[s[i]] = true
	}

	return string(stack)
}

func main() {
	s := "cbacdcbc"
	fmt.Println("Smallest subsequence is:", smallestSubsequence(s))
}

在这些例子中，贪心策略的选择是关键：在活动选择问题中，我们选择结束时间最早的活动；在分数背包问题中，我们选择单位价值最高的物品；在最小字典序问题中，我们选择在保持字典序最小的同时，能够保留的字符。这些策略都是基于问题的特定性质，而且通常需要通过数学证明来验证它们是否能够确保得到全局最优解。

hot-100

贪心算法

例子 1：活动选择问题

例子 2：分数背包问题

例子 3：最小的字典序