贪心算法的思想
即对于目标T，对于达成它的每一局部都选择最优选项，直到满足或最终近似满足为止，最终结果或许不是全局最优解，但应该是近似最优解，因为它足够简单。
每一步都采取局部最优做法！
贪婪算法大多时候都是近似最优算法！
贪心算法的三步走：
第一步：明确到底什么是最优解？
第二步：明确什么是子问题的最优解？
第三步：分别求出子问题的最优解再堆叠出全局最优解？
贪心算法的前提：
- 原问题复杂度过高；
- 求全局最优解的数学模型难以建立；
- 求全局最优解的计算量过大；
- 没有太大必要一定要求出全局最优解，“比较优”就可以。
以上情况几乎99.99999999999%就要使用贪心算法的思想来解决问题！
分解子问题的方法：
1.按串行任务分：时间串行的任务，按子任务来分解，即每一步都是在前一步的基础上再选择当前的最优解。
2.按规模递减分：规模较大的复杂问题，可以借助递归思想，分解成一个规模小一点点的问题，循环解决，当最后一步的求解完成后就得到了所谓的“全局最优解”。
3.按并行任务分：这种问题的任务不分先后，可能是并行的，可以分别求解后，再按一定的规则(比如某种配比公式)将其组合后得到最终解。
如何知道贪心算法结果逼近全局最优解？
正因为有些问题很难求到全局最优解，才有贪心算法，它需要考虑成本、速度、价值： 成本：耗费多少资源，花掉多少编程时间。 速度：计算量是否过大，计算速度能否满足要求。 价值：得到了最优解与次优解是否真的有那么大的差别，还是说差别可以忽略。
例题
0-1背包问题 有一个背包，最多能承载150斤的重量，现在有7个物品， 重量分别为[35, 30, 60, 50, 40, 10, 25]， 它们的价值分别为[10, 40, 30, 50, 35, 40, 30]， 每个物品要么选择要么放弃， 应该如何选择才能使得我们的背包背走最多价值的物品？
解法:
-
第一步：明确到底什么是最优解？ —— 在重量限制内，价值最大的就是最优解；
-
第二步：明确什么是子问题的最优解？这就是"局部最优解"
- 方案一：每一次都尽量选择当前价值最高的物品
- 方案二：每次尽量选择重量最小的物品
- 方案三：每次尽量选择价值密度高的物品，即单位重量价值高的物品
-
第三步：分别求出子问题的最优解再堆叠出全局最优解？
解题步骤及Go语言描述：
方案一：按照制订的规则(价值)进行计算，数组索引顺序是：3 1 5 4 ；最终的总重量是：130 ；最终的总价值是：165。
方案二：按照制订的规则(重量)进行计算，数组索引顺序是：5 6 1 0 4 ；最终的总重量是：140；最终的总价值是：155。可以看到，重量优先是没有价值优先的策略更好。
方案三：按照制订的规则(单位密度)进行计算，数组索引顺序是：5 1 6 3 4；最终的总重量是：150；最终的总价值是：170。可以看到，单位密度这个策略比之前的价值策略和重量策略都要好。
type good struct {
// name string
weight int
price int
status int // 0未选中，1已选中
}
var maxWeight = 150
var goods = []good{
good{35, 10, 0},
good{30, 40, 0},
good{60, 30, 0},
good{50, 50, 0},
good{40, 35, 0},
good{10, 40, 0},
good{25, 30, 0},
}
// 解法一：每一次都尽量选择当前价值最高的物品
// 按照制订的规则(价值)进行计算，数组索引顺序是：3 1 5 4 ；最终的总重量是：130 ；最终的总价值是：165。
func GreedyKnapsack1(goods []good, maxW int) (totalP, totalW int) {
// 物品总数
n := len(goods)
// 选物品
for totalW <= maxW {
// 选出余下价格最大的物品
maxPIndex := -1
maxPrice := goods[0].price
for i := 0; i < n; i++ {
if goods[i].status == 0 && goods[i].price > maxPrice {
maxPIndex = i
maxPrice = goods[i].price
}
}
// 如计算超出重量则退出
if totalW+goods[maxPIndex].weight > maxW {
break
}
// 累计
goods[maxPIndex].status = 1
totalW += goods[maxPIndex].weight
totalP += goods[maxPIndex].price
fmt.Println("select good:", goods[maxPIndex], ",index:", maxPIndex, ",total weight:", totalW)
}
fmt.Println("goods:", goods)
return
}
// 解法二：每次尽量选择重量最小的物品
// 按照制订的规则(重量)进行计算，数组索引顺序是：5 6 1 0 4 ；最终的总重量是：140；最终的总价值是：155。可以看到，重量优先是没有价值优先的策略更好。
func GreedyKnapsack2(goods []good, maxW int) (totalP, totalW int) {
// 物品总数
n := len(goods)
// 选物品
for totalW <= maxW {
minWIndex := -1
minWeight := math.MaxInt64
// 选出余下重量最小的
for i := 0; i < n; i++ {
if goods[i].status == 0 && goods[i].weight <= minWeight {
minWIndex = i
minWeight = goods[i].weight
}
}
// 如计算超出重量则退出
if totalW+goods[minWIndex].weight > maxW {
break
}
// 累计
goods[minWIndex].status = 1
totalW += goods[minWIndex].weight
totalP += goods[minWIndex].price
fmt.Println("select good:", goods[minWIndex], ",index:", minWIndex, ",total weight:", totalW)
}
fmt.Println("goods:", goods)
return
}
// 解法三：每次尽量选择价值密度高的物品，即单位重量价值高的物品
// 按照制订的规则(单位密度)进行计算，数组索引顺序是：5 1 6 3 4；最终的总重量是：115；最终的总价值是：160。可以看到，单位密度这个策略比之前的价值策略和重量策略都要好。
func GreedyKnapsack3(goods []good, maxW int) (totalP, totalW int) {
// 物品总数
n := len(goods)
// 选物品
for totalW <= maxW {
maxDIndex := -1
maxDensity := 0.0
// 选出余下价格密度最高的
for i := 0; i < n; i++ {
if goods[i].status == 0 && float64(goods[i].price) / float64(goods[i].weight) > maxDensity {
maxDIndex = i
maxDensity = float64(goods[i].price) / float64(goods[i].weight)
}
}
// fmt.Println("maxDIndex:",maxDIndex)
// fmt.Println("maxDensity:",maxDensity)
// 如计算超出重量则退出
if totalW+goods[maxDIndex].weight > maxW {
break
}
// 累计
goods[maxDIndex].status = 1
totalW += goods[maxDIndex].weight
totalP += goods[maxDIndex].price
fmt.Println("select good:", goods[maxDIndex], ",index:", maxDIndex, ",total weight:", totalW)
}
fmt.Println("goods:", goods)
return
}
很显然大多数方案不是全局最优解，但只要是近似最优解。优点就是计算简单，对于那些计算精确解需要极大代价的算法来说，贪心算法求解出近似解是不错的选择。
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
