贪婪算法，也称为贪婪算法，意味着在解题时，总是在目前做出最好的选择。 也就是说，不是从整体最佳考虑，他所做的只是某种意义上的局部最佳解。 算法并不能对所有问题都得到整体最优解，但对于相当广泛的许多问题他都能产生整体最优解或整体最优解的近似解。
基本想法：
为说明问题建立数学模型。
将解题分为几个子问题。
求解各子问题，得到子问题的局部最优解。
将子问题解的局部最优解合成原解问题的一个解。
这个算法有问题：
1 .不能保证求出的最后的解是最佳的
2 .不能用于求最大或最小解
3 .只能求出满足某些限制条件的可行解的范围。
实现该算法的过程：
从问题的初始解出发
while可以朝着给定的总目标进一步do
求可行解的一个解元素；
将所有解元素组合起来作出问题的可行解。
贪婪选择的性质：
贪婪选择的性质是指寻求问题的整体最优解可以通过一系列局部最优选择来实现。 换句话说，在考虑做出什么样的选择时，我们只考虑对当前问题的最佳选择，而不考虑子问题的结果。 这是贪婪算法可能的第一个基本要素。 贪婪算法迭代地做出一个又一个贪婪的选择，每次做出贪婪的选择，都将所求问题简化为更小规模的子问题。 对于一个具体问题，要判断它是否具有贪婪选择的性质，必须证明每一步所进行的贪婪选择最终会导致问题的整体最优解。
最佳子结构性质：
如果某个问题的最优解包含其子问题的最优解，则称该问题具有最优子结构的性质。 问题的最优子结构性质是该问题可以用贪婪算法求解的重要特征。
贪婪法的一般流程
greedy(c )/c是作为问题输入集合的候补集合
{
S={ }； //初始解集合为空集合
while(notsolution(s ) )//集合s不构成问题的一个解
{
x=select(c； //在候选集合c中做出贪婪的选择
判断在iffeasible(s，x )//集合s上加上x的解是否可能
S=S {x}；
C=C-{x}；
}
返回s；
例题分析[事件调度问题]事件调度问题是用贪婪算法有效求解的一个很好的例子。 这个问题要求有效安排争夺某种公共资源的一系列活动。 贪婪算法提供了简单干净的方法，允许尽可能多的活动兼容使用公共资源。
有n个事件的集合e={ 1，2，n}，每个事件都要求使用相同的资源，例如演讲会场，但在同一时间内只能使用一个事件。 每个活动I都有请求使用资源的开始时间si和结束时间fi，si fi。 如果选择了活动I，则在半开时间段[si，fi]内消耗资源。 据说如果区间[si，fi]和区间[sj，fj]不相交，则活动I和活动j具有互换性。 也就是说，在sifi或sjfj的情况下，活动I与活动j兼容。 活动调度的问题是从给定的活动集合中选择最大的兼容活动子集合。
在求解事件放置问题的贪婪算法gpeedyselector中，每个事件的开始时间和结束时间存储在数组s和f{中，按结束时间的非减法顺序排列。 f1F2…fn排列。 如果给定活动未按此顺序排列，则可以按o(nlogn )时间进行排序。
//*
*活动日程
*/
@Test
public void testArrangeActivity (
int [ ] start={ 1，3，0，5，3，5，6，8，8，2，12 }；
int [ ] end={ 4，5，6，7，8，9，10，11，12，13，14 }；
listintegerresults=arrange activity (start，end )；
for(intI=0； i results.size (； I ) {
intindex=results.get(I；
System.out.println ('开始时间：' start[index]，结束时间：' end[index] )；
}
}
//*
事件时间表
*
* @param s开始时间
* @param e结束时间
* @return
*/
publiclistintegerarrangeactivity (int [ ] s，int[] e ) {
int total=s.length；
int endFlag=e[0]；
列表集成器
gt; results = new ArrayList<>();results.add(0);
for (int i = 0; i < total; i++) {
if (s[i] > endFlag) {
results.add(i);
endFlag = e[i];
}
}
return results;
}
[找零钱问题]假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，诶99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。
@Test
public void testGiveMoney() {
//找零钱
int[] m = {25, 10, 5, 1};
int target = 99;
int[] results = giveMoney(m, target);
System.out.println(target + "的找钱方案:");
for (int i = 0; i < results.length; i++) {
System.out.println(results[i] + "枚" + m[i] + "面值");
}
}
public int[] giveMoney(int[] m, int target) {
int k = m.length;
int[] num = new int[k];
for (int i = 0; i < k; i++) {
num[i] = target / m[i];
target = target % m[i];
}
return num;
}
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
记得当时学算法的时候，就是这个例子，可以说很经典。
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量，即∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略?
贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。但是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于本例题中的3种贪心策略，都无法成立，即无法被证明，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。比如，求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
［均分纸牌］有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张,但纸牌总数必为n的倍数.可以在任一堆上取若干张纸牌,然后移动。移牌的规则为：在编号为1上取的纸牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如：n=4，4堆纸牌分别为：① 9 ② 8 ③ 17 ④ 6 移动三次可以达到目的：从③取4张牌放到④ 再从③区3张放到②然后从②去1张放到①。
输入输出样例：4
9 8 17 6
屏幕显示：3
算法分析：设a[i]为第I堆纸牌的张数（0<=I<=n），v为均分后每堆纸牌的张数，s为最小移动次数。
我们用贪心算法，按照从左到右的顺序移动纸牌。如第I堆的纸牌数不等于平均值，则移动一次（即s加1），分两种情况移动：
1．若a[i]>v，则将a[i]-vqfdbg第I堆移动到第I+1堆；
2．若a[i]< v，则将v-a[i]qfdbg第I+1堆移动到第I堆。为了设计的方便，我们把这两种情况统一看作是将a[i]-v从第I堆移动到第I+1堆，移动后有a[i]=v; a[I+1]=a[I+1]+a[i]-v.
在从第I+1堆取出纸牌补充第I堆的过程中可能回出现第I+1堆的纸牌小于零的情况。
如n=3，三堆指派数为1 2 27 ，这时v=10，为了使第一堆为10，要从第二堆移9张到第一堆，而第二堆只有2张可以移，这是不是意味着刚才使用贪心法是错误的呢？
我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的，我们在移动过程中，只是改变了移动的顺序，而移动次数不便，因此此题使用贪心法可行的。
@Test
public void testMoveCard() {
//总共4堆
int heap = 4;
// int[] cards = {9, 8, 17, 6};
int[] cards = {10, 10, 20, 0};
int count = moveCards(cards, heap);
System.out.println("移动次数:" + count);
for (int i = 0; i < cards.length; i++) {
System.out.println("第" + (i + 1) + "堆牌数:" + cards[i]);
}
}
/**
* 均分纸牌
* @param cards
* @param heap
* @return
*/
public int moveCards(int[] cards, int heap) {
//总牌数
int sum = 0;
for (int i = 0; i < cards.length; i++) {
sum += cards[i];
}
//每堆平均牌数
int avg = sum / heap;
//移动次数
int count = 0;
for (int i = 0; i < cards.length; i++) {
if(cards[i] != avg) {
int moveCards = cards[i] - avg;
cards[i] -= moveCards;
cards[i + 1] += moveCards;
count++;
}
}
return count;
}
利用贪心算法解题，需要解决两个问题：
一是问题是否适合用贪心法求解。我们看一个找币的例子，如果一个货币系统有三种币值，面值分别为一角、五分和一分，求最小找币数时，可以用贪心法求解；如果将这三种币值改为一角一分、五分和一分，就不能使用贪心法求解。用贪心法解题很方便，但它的适用范围很小，判断一个问题是否适合用贪心法求解，目前还没有一个通用的方法，在信息学竞赛中，需要凭个人的经验来判断。
二是确定了可以用贪心算法之后，如何选择一个贪心标准，才能保证得到问题的最优解。在选择贪心标准时，我们要对所选的贪心标准进行验证才能使用，不要被表面上看似正确的贪心标准所迷惑，如下面的例子。
［最大整数］设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。
输入：n
N个数
输出：连成的多位数
算法分析：此题很容易想到使用贪心法，在考试时有很多同学把整数按从大到小的顺序连接起来，测试题目的例子也都符合，但最后测试的结果却不全对。按这种标准，我们很容易找到反例：12，121应该组成12121而非12112，那么是不是相互包含的时候就从小到大呢？也不一定，如12，123就是12312而非12123，这种情况就有很多种了。是不是此题不能用贪心法呢？
其实此题可以用贪心法来求解，只是刚才的标准不对，正确的标准是：先把整数转换成字符串，然后在比较a+b和b+a，如果a+b>=b+a，就把a排在b的前面，反之则把a排在b的后面。
@Test
public void testMaxNum() {
//有n个正整数，将它们连接成一排，组成一个最大的多位整数
//12112错误
//12121正解
// int[] nums = {12, 121};
int[] nums = {12, 123};
String result = maxNum(nums);
System.out.println("组成最大整数:" + result);
}
/**
* 根据给定的整数组成最大的多位数
* @param nums
*/
public String maxNum(int[] nums) {
String result = "";
for (int i = 0; i < nums.length; i++) {
String num1 = nums[i] + "";
for (int j = 1; j < nums.length; j++) {
String num2 = nums[j] + "";
if ((num1 + num2).compareTo(num2 + num1) < 0) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
for (int i = 0; i < nums.length; i++) {
result += nums[i];
}
return result;
}
贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。
————————————————
版权声明：本文为CSDN博主「别再想更好的办法」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37763204/article/details/79289532