前言
贪心算法(greedy algorithm,又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。下面,我们详细介绍。
1. 概念
贪婪算法(Greedy)的定义:是一种在每一步选中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法。当下做局部最优判断,不能回退(能回退的是回溯,最优+回退是动态规划),回溯和动态规划后面会讲到。
由于贪心算法的高效性以及所求得答案比较接近最优结果,贪心算法可以作为辅助算法或解决一些要求,结果不特别精确的问题。注意:当下是最优的,并不一定全局是最优的。
举例如下:
-
有硬币分值为10、9、4若干枚,问如果组成分值18,最少需要多少枚硬币?
采用贪心算法,选择当下硬币分值最大的:10
18-10=8
8/4=2
即:1个10、2个4,共需要3枚硬币
实际上我们知道,选择分值为9的硬币,2枚就够了
18/9=2 -
如果改成有硬币分值为10、5、1若干枚,问如果组成分值16,最少需要多少枚硬币?
采用贪心算法,选择当下硬币分值最大的:10
16-10=6
6-5=1
即:1个10,1个5,1个1 ,共需要3枚硬币,即为最优解
由此可以看出贪心算法适合于一些特殊的情况,如果能用一定是最优解。
2. 经典问题
背包问题是算法的经典问题,分为部分背包和0-1背包,主要区别如下:
部分背包:某件物品是一堆,可以带走其一部分
0-1背包:对于某件物品,要么被带走(选择了它),要么不被带走(没有选择它),不存在只带走一部分的情况。
部分背包问题可以用贪心算法求解,且能够得到最优解。
假设一共有N件物品,第 i 件物品的价值为 Vi ,重量为Wi,一个小偷有一个最多只能装下重量为W的背包,他希望带走的物品越有价值越好,可以带走某件物品的一部分,请问:他应该选择哪些物品?
假设背包可容纳50Kg的重量,物品信息如下表:
物品 | 重量(kg) | 价值(元) | 单位重量的价值(元/kg) |
---|---|---|---|
A | 10 | 60 | 6 |
B | 20 | 100 | 5 |
C | 30 | 120 | 4 |
贪心算法的关键是贪心策略的选择。将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品。按照我们的贪心策略,单位重量的价值排序: 物品A > 物品B > 物品C
因此,我们尽可能地多拿物品A,直到将物品1拿完之后,才去拿物品B,然后是物品C 可以只拿一部分…
2.2 代码实现
2.2.1 定义商品类
package org.wanlong.algorithm;
/**
* @author wanlong
* @version 1.0
* @description:
* @date 2023/6/16 14:21
*/
public class Goods {
String name;
double weight;
double price;
double val;
public Goods(String name,double weight, double price) {
this.name=name;
this.weight = weight;
this.price = price;
val=price/weight;
}
}
2.2.2 贪心算法实现
package org.wanlong.algorithm;
import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Collectors;
/**
* @author wanlong
* @version 1.0
* @description: 贪心算法
* @date 2023/6/16 14:20
*/
public class Greedy {
double bag;
public void take(Goods[] goodslist) {
// 对物品按照价值排序从高到低
Goods[] goodslist2 = sort(goodslist);
double sum_w = 0;
//取出价值最高的
for (int i = 0; i < goodslist2.length; i++) {
sum_w += goodslist2[i].weight;
if (sum_w <= bag) {
System.out.println(goodslist2[i].name + "取" + goodslist2[i].weight + "kg");
} else {
System.out.println(goodslist2[i].name + "取" + (bag - (sum_w - goodslist2[i].weight)) + "kg");
return;
}
}
}
// 按物品的每kg价值排序 由高到低 price/weight
private Goods[] sort(Goods[] goodslist) {
Arrays.sort(goodslist, 0, goodslist.length , new Comparator<Goods>() {
@Override
public int compare(Goods o1, Goods o2) {
double i = o2.val - o1.val;
if (i > 0) {
return 1;
} else if (i == 0) {
return 0;
} else {
return -1;
}
}
});
return goodslist;
}
public static void main(String[] args) {
Greedy bd = new Greedy();
Goods goods1 = new Goods("A", 10, 60);
Goods goods2 = new Goods("B", 20, 100);
Goods goods3 = new Goods("C", 30, 120);
Goods[] goodslist = {goods1, goods3, goods2};
bd.bag = 50;
bd.take(goodslist);
}
}
3. 时间复杂度
在不考虑排序的前提下,贪心算法只需要一次循环,所以时间复杂度是O(n)
4. 优缺点
优点:性能高,能用贪心算法解决的往往是最优解
缺点:在实际情况下能用的不多,用贪心算法解的往往不是最好的文章来源:https://www.toymoban.com/news/detail-490757.html
5. 适用场景
针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大。
每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据(局部最优而全局最优)
大部分能用贪心算法解决的问题,贪心算法的正确性都是显而易见的,也不需要严格的数学推导证明,在实际情况下,用贪心算法解决问题的思路,并不总能给出最优解。文章来源地址https://www.toymoban.com/news/detail-490757.html
到了这里,关于18. 算法之贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!