ThinkerQAQ

NOTE

3.3 贪心

1. 是什么 - 每一步都采取当前状态下的最优选择（局部最优解），从而希望推导出全局最优解 2. 举例 2.1. 最优装载 2.1.1. 思路 - 每次都选择重量最小的装上船 2.1.2. 实现 2.1.2.1. 测试 2.2. 零钱兑换 - 假设有 25 分、10 分、5 分、1 分的硬币，现要找

Data Structures & Algorithms创建于 更新于 historical

这是历史学习笔记，可能存在过时或不完整的理解。

1. 是什么

  • 每一步都采取当前状态下的最优选择（局部最优解），从而希望推导出全局最优解

2. 举例

2.1. 最优装载

2.1.1. 思路

  • 每次都选择重量最小的装上船

2.1.2. 实现

import (
	"fmt"
	"sort"
)

func Pirate() {
	weight := []int{3, 5, 4, 10, 7, 14, 2, 11}
	sort.Ints(weight)
	remainWeight := 30
	result := make([]int, 0)
	for _, w := range weight {
		remainWeight -= w
		if remainWeight < 0 {
			break
		}
		result = append(result, w)
	}
	fmt.Println(result)
}
2.1.2.1. 测试
func TestPirate(t *testing.T) {
	Pirate()
}

2.2. 零钱兑换

  • 假设有 25 分、10 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少？

2.2.1. 思路

  • 每次选择面值最大的硬币

2.2.2. 实现


import (
	"fmt"
	"sort"
)

func CoinChange() {
	coinFace := []int{25, 10, 5, 1}
	changeMoney := 41
	sort.Slice(coinFace, func(i, j int) bool {
		return i < j
	})

	result := make([]int, 0)
	for i := 0; i < len(coinFace); i++ {
		if changeMoney-coinFace[i] < 0 {
			continue
		} else {
			changeMoney -= coinFace[i]
			result = append(result, coinFace[i])
			i--
		}

	}

	fmt.Println(result)
}

2.2.3. 测试

func TestCoinChange(t *testing.T) {
	CoinChange()
}

2.3. 0-1背包

2.3.1. 思路

  • 每次选取价值最大的物品

2.3.2. 实现


import (
	"fmt"
	"sort"
)

type Article struct {
	//重量
	weight int
	//价值
	value int
}

func (a *Article) String() string {
	return fmt.Sprintf("[w%v:v%v]", a.weight, a.value)
}

func NewArticle(weight int, value int) *Article {
	return &Article{weight: weight, value: value}
}

func Knapsack() {
	articles := []*Article{
		NewArticle(35, 10),
		NewArticle(30, 40),
		NewArticle(60, 30),
		NewArticle(50, 50),
		NewArticle(40, 35),
		NewArticle(10, 40),
		NewArticle(25, 30),
	}
	sort.Slice(articles, func(i, j int) bool {
		return articles[i].value > articles[j].value
	})

	result := make([]*Article, 0)
	remainWeight := 150
	for _, a := range articles {
		remainWeight -= a.weight
		if remainWeight < 0 {
			break
		}
		result = append(result, a)
	}

	fmt.Println(result)
}
2.3.2.1. 测试
func TestKnapsack(t *testing.T) {
	Knapsack()
}

2026 注：一般的 0-1 背包不能用“每次选择价值最大的物品”保证全局最优，这里保留当时的贪心理解。

3. 参考