❶ 贪心算法的证明方法
贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
----------------------------------------------
其实归纳起来也就一个类。其他的都是分支
❷ 请问数钱的贪婪算法怎样确保得到最优解
贪婪算法：总是作出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。
（注：贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解。但其解必然是最优解的很好近似解。
基本思路：——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
基本要素：
1、 贪婪选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪婪选择来达到。（与动态规划的主要区别）
采用自顶向下，以迭代的方式作出相继的贪婪选择，每作一次贪婪选择就将所求问题简化为一个规模更小的子问题。
对于一个具体问题，要确定它是否具有贪婪选择的性质，我们必须证明每一步所作的贪婪选择最终导致问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪婪选择开始的，而且作了贪婪选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪婪选择，最终可得到问题的一个整体最优解。
2、最优子结构性质:包含子问题的最优解
1、 设有n个活动的安排，其中每个活动都要求使用同一资源，如演讲会场，而在同一时间只允许一个活动使用这一资源。每个活动都有使用的起始时间和结束时间。问：如何安排可以使这间会场的使用率最高。
活动 起始时间 结束时间
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 10
8 8 11
9 8 12
10 2 13
11 12 14
算法：一开始选择活动1，然后依次检查活动一i是否与当前已选择的所有活动相容，若相容则活动加入到已选择的活动集合中，否则不选择活动i,而继续检查下一活动的相容性。即：活动i的开始时间不早于最近加入的活动j的结束时间。
Prodere plan;
Begin
n:=length[e];
a {1};
j:=1;
for i:=2 to n do
if s[i]>=f[j] then
begin a a∪{i};
j:=i;
end
end;
例1 [找零钱] 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。
假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，否则硬币的选择将不可行（零钱总数超过6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后加入两个1美分的硬币。
贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习1）。
❸ 贪心算法总结
做了这10道题，其实发现贪心算法没有什么规律，要说有什么共同特点就是都是由局部最优从而推出全局最优，每个题基本上都要考虑其局部最优是什么，其全局最优是什么，所以虽然都用到了贪心算法的思想，但是题与题之间又没有什么规律可言。
现在把这10道题的思路总结一下（总结主要以我的主观看法在写，可能别人看会不知道我在说什么）
1.分发饼干：
https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html
思路：想要完成最多的小孩满足，那么就得最小的饼干给胃口最小的小孩
这里的贪心思想，
局部最优就是尽可能让一个饼干喂饱一个
全局最优就是最多的小孩满足
2.摆动序列：
https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html
思路：这里要找到最长的摆动序列，那么其实就是找那些波峰波谷，如图所示
可以看出来，在到达波峰波谷的路上有几个数字不会影响什么，可以直接去掉。
那么这里的局部最优就是把单调坡上的点删掉，保留最多的波峰波谷
全局最优就是得到对多的波峰波谷，即最长的摆动序列
3.最大子序和
https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html
这道题显然可以暴力解出来，即列出所有子序和，找出最大的，不过计算量会比贪心大很多。
这里主要介绍贪心解的思想：
想要得到最大子序和，就得保证每次相加时，相加后不能为负数，因为负数继续往下加一定是拉低总和的，那么我们当加成到负数时就重新从下个数开始加，并实时记录最大的子序和，这样一遍循环就能得出最大子序和。
局部最优：加成负数就立刻停止，并从下个元素重新开始
全局最优：得到最大子序和
4.买卖股票的最佳时机II
https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html
思路：想要得到最大利润，那就要低价买入高价卖出，那么怎样的买卖才能得到最大利润呢。
这里就体现出贪心算法的“贪”字（我猜的），这道题贪在哪呢，贪在只要有利可图就去做，即只要今天买入的价钱比明天卖出的价钱底，即有利可图，那么我就去做，做就是在今天买入，在明天卖出。
局部最优：得到每天的最大正利润
全局最优：得到最大利润
5.跳跃游戏
https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
思路：每个数组的元素代表的是可以跳的最远下标，那么我们只要使那个最远下标包含最后一个下标就是可以跳到，那么我们每跳到一个位置就要更新那个可以跳的范围，即可以跳到的最远下标。
局部最优：每次跳跃都得出最远的跳跃范围
全局最优：最后能跳到的最大范围
6.跳跃游戏II
https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
思路：这道题要得到最小的跳跃数，其实只要保证跳的是位置是可以跳范围内更新最远范围的位置就可以了。
为什么这么说呢？以题例来说：
我们刚开始在‘0’的位置，我们能跳到‘1’和‘2’的位置，那么我们怎么跳呢？可以看到跳到‘1’之后更新的最大范围是‘4’，跳到‘2’之后更新的最大范围是‘3’，所以我们就跳‘2’了，因为跳‘1’之后更新的最大可跳范围更大包含了跳‘2’的最大可跳范围，那么肯定是跳‘3’最优呀，这里就体现了局部最优的思想。
局部最优：每次跳后，更新的最大可调范围最大
全局最优：跳跃次数最少
7.K次取反后最大化的数组和
https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html
思路：想要得到最大数组和，我们就可以想到怎样做呢？
一，尽可能保证负数最少
二，负数绝对值大的优先变正
三，正数绝对值小的优先变负，有零变零
本着这三条原则做，就能做出来。
那么这道题体现了什么贪心思想呢？
我感觉，前面那三条都是贪心中‘贪’的体现
在负数中，局部最优就是：绝对值大的负数优先变正
在正数中，局部最优就是：绝对值小的正数变负，有零变零
得到的全局最优：数组和最大
8.加油站
https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
思路：首先可以想到这道题是可以暴力解出来了，即分别以每个加油站为起点，得出可以跑一圈的加油站
那么贪心思想做，该怎么做呢，首先可以想到，如果以一个1点为起点当跑着跑着跑到3，油变为负数时，那么说明以这个起点是不行的，但是以2或3为起点行不行呢？答案肯定是不行的，因为1跑到3，油变为负，说明1~3的gas=0的，所以可以得出，如果1~3油数变为负数，那么由2~3油数肯定也为负数。
所以这里就可以得出，如果经过几个加油站油数变为负了，那么起点就更新为这一段路的下个加油站跑
局部最优：油量一旦为负，就从下个加油站重新跑
全局最优：得出可以跑一圈的加油站起点
9.分发糖果
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
思路：每个孩子至少一个，如果一个孩子比他旁边的孩子优秀，就要比他旁边的糖果多，这道题一旦两边都考虑很容易顾此失彼，所以我们就定义两个循环，分别从左到右，从右到左去考虑，只要更优秀则比他旁边的多1，如果已经多了就不用变了。
局部最优：保证优秀的孩子比他旁边的孩子糖果多
全局最优：满足题中条件，至少要发的糖果
10.柠檬水找零
https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html
思路：我们在找零时要遵守的规则一定是：
5 得5
10 得10减5
15 得15，优先减一个10减一个5 如果10块没有则减三个5
局部最优：以最少用的5块的方式找零
全局最优：得到找零能否进行下去
❹ 数据结构之贪心算法
贪婪算法（Greedy）的定义：是一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
贪婪算法：当下做局部最优判断，不能回退
（能回退的是回溯，最优+回退是动态规划）
由于贪心算法的高效性以及所求得答案比较接近最优结果，贪心算法可以作为辅助算法或解决一些要求
结果不特别精确的问题
注意：当下是最优的，并不一定全局是最优的。举例如下：
有硬币分值为10、9、4若干枚，问如果组成分值18，最少需要多少枚硬币？
采用贪心算法，选择当下硬币分值最大的：10
18-10=8
8/4=2
即：1个10、2个4，共需要3枚硬币
实际上我们知道，选择分值为9的硬币，2枚就够了
18/9=2
如果改成：
背包问题是算法的经典问题，分为部分背包和0-1背包，主要区别如下：
部分背包：某件物品是一堆，可以带走其一部分
0-1背包：对于某件物品，要么被带走（选择了它），要么不被带走（没有选择它），不存在只带走一部分的情况。
部分背包问题可以用贪心算法求解，且能够得到最优解。
假设一共有N件物品，第 i 件物品的价值为 Vi ，重量为Wi，一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，可以带走某件物品的一部分，请问：他应该选择哪些物品？
假设背包可容纳50Kg的重量，物品信息如下表：
将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品
按照我们的贪心策略，单位重量的价值排序： 物品A > 物品B > 物品C
因此，我们尽可能地多拿物品A，直到将物品1拿完之后，才去拿物品B，然后是物品C 可以只拿一部分.....
在不考虑排序的前提下，贪心算法只需要一次循环，所以时间复杂度是O(n)
优点：性能高，能用贪心算法解决的往往是最优解
缺点：在实际情况下能用的不多，用贪心算法解的往往不是最好的
针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据（局部最优而全局最优）
大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明
在实际情况下，用贪心算法解决问题的思路，并不总能给出最优解
❺ 高分悬赏贪心算法的作业
一、算法思想
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
二、例题分析
1、[背包问题]有一个背包，背包容量是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）每次选取单位容量价值最大的物品，成为解本题的策略。 ?
2、[单源最短路径]一个有向图G，它的每条边都有一个非负的权值c[i,j]，“路径长度”就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径。
E.Dijkstra发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出最短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。
设置顶点集合S并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S。初始时S中只含源。
设u为G中一顶点，我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到u特殊路径，并把这个特殊路径记录下来（例如程序中的dist[i，j]）。
每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长度进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解 。
stra.pas
3、[机器调度]现有N项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间和完成时间有下表：
任务 a b c d e f g
开始(si) 0 3 4 9 7 1 6
完成(fi) 2 7 7 11 10 5 8
在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少的可行分配方案。请就本题给出的条件，求出最优分配。
?三、练习题：
已知5个城市之间有班机传递邮件，目的是为了寻找一条耗油量较少的飞行路线。5个城市的联系网络如图所示。图中编号的结点表示城市，两个城市之间的连线上的值表示班机沿该航线已行的耗油量，并假定从城市i到j和城市j到i之间的耗油量是相同的。
分析：
1. 运用贪心思想：
在每一步前进的选择上，选取相对当前城市耗油量最小的航线；
2. 图解：若从1出发，有图：
总耗油量=14 1-2-5-3-4-1
但若路线改为：1-5-3-4-2-1，则总耗油量=13
所以，这样的贪心法并不能得出最佳解。
3. 改善方案：
从所有城市出发的信心过程，求最优的。
编程：
1. 数据结构：
城市联系网络图的描述(图的邻接矩阵的描述)：
const
c=array[1..5,1..5] of integer=((0,1,2,7,5),
(1,0,4,4,3),
(2,4,0,1,2),
(7,4,1,0,3));
2. 贪心过程：
begin
初始化所有城市的算途径标志；
设置出发城市V；
for i:=1 to n-1 do {n-1个城市}
begin
s:=从V至所有未曾到过的城市的边集中耗油量最少的那个城市；
累加耗油量；
V:=s；
设V城市的访问标志；
end;
最后一个城市返回第一个城市，累加耗油量；
end;
3. 主过程：实现改善方案
begin
for i:=1 to n do
begin
cost1:=maxint; {初始化}
调用贪心过程，返回本次搜索耗油量cost；
if cost<cost1 then 替换；
end;
输出；
end
❻ 关于编程的贪心法
定义
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
[编辑本段]贪心算法的基本思路
1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[编辑本段]例题分析
[背包问题]有一个背包，背包容量是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，则答案错误。 【注意：如果物品可以分割为任意大小，那么策略3可得最优解】 对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。 但是，如果题目是如下所示，这个策略就也不行了。 W=40 物品：A B C 重量：28 20 15 价值：28 20 15 附：本题是个NP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
[编辑本段]备注
贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。 所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）
[编辑本段]附贪心算法成功案例之一
马踏棋盘的贪心算法 123041-23 XX 【问题描述】 马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。 【初步设计】 首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下： 1、 输入初始位置坐标x,y； 2、 步骤 c: 如果c> 64输出一个解，返回上一步骤c-- (x,y) ← c 计算(x,y)的八个方位的子结点，选出那此可行的子结点 循环遍历所有可行子结点，步骤c++重复2 显然（2）是一个递归调用的过程，大致如下： void dfs(int x,int y,int count) { int i,tx,ty; if(count> N*N) { output_solution();//输入一个解 return; }