今天是集训第二天，我们学习了复杂贪心算法
贪心算法是一种非常常见的算法，它的简单和高效性使其在实际应用中被广泛使用。
贪心算法的核心思想是在每一步都采取当前状态下最优的选择，而不考虑未来可能产生的影响。
虽然贪心算法不能保证总是得到最优解，但在很多情况下，它可以获得很好的结果。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。
我将介绍贪心算法的基本概念和一些经典应用，以及如何通过贪心算法来解决一些实际问题。希望通过本文的阅读，你们可以对贪心算法有更加深刻的理解，并能够在实际问题中应用贪心算法来解决一些问题
如何理解“贪心算法”？
关于贪心算法，我们先看一个例子。
假设我们有一个可以容纳100kg物品的背包，可以装各种物品。我们有以下5种豆子，每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？
实际上，这个问题很简单，我估计你一下子就能想出来，没错，我们只要先算一算每个物品的单价，按照单价由高到低依次来装就好了。单价从高到低排列，依次是：黑豆、绿豆、红豆、青豆、黄豆，所以，我们可以往背包里装20kg黑豆、30kg绿豆、50kg红豆。
这个问题的解决思路显而易见，它本质上借助的就是贪心算法。结合这个例子，我总结一下贪心算法解决问题的步骤，我们一起来看看。
第一步，当我们看到这类问题的时候，首先要联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
类比到刚刚的例子，限制值就是重量不能超过100kg，期望值就是物品的总价值。这组数据就是5种豆子。我们从中选出一部分，满足重量不超过100kg，并且总价值最大。
第二步，我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
类比到刚刚的例子，我们每次都从剩下的豆子里面，选择单价最高的，也就是重量相同的情况下，对价值贡献最大的豆子。
第三步，我们举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下，举几个例子验证一下就可以了。严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。而且，从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。
实际上，用贪心算法解决问题的思路，并不总能给出最优解。
示例一：背包问题
- 问题描述：
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
- 问题分析：
- 目标函数：
∑pi求和，最大，使得装入背包中的所有物品 pi 的价值加起来最大； - 约束条件：装入的物品总重量不超过背包容量：
∑wi <= M( M=150); - 贪心策略：
1、选择价值最大的物品。
2、选择重量最小的物品。
3、选择单位重量价值最大的物品。
1、值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
2、贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
3、可惜的是，它需要证明后才能真正运用到题目的算法中。
- 一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
- 对于背包问题中的 3 种贪心策略，都是 无法成立（无法被证明） 的，解释如下：
（1）选取价值最大者：
- W=30
| 物品 | 重量 | 价值 |
|---|---|---|
| A | 28 | 30 |
| B | 12 | 20 |
| C | 12 | 20 |
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B和C一起，则更好。
（2）选取重量最小者：选取重量最小。它的反例与第一种策略的反例差不多。
（3）选取单位重量价值最大者：
- W=30
| 物品 | 重量 | 价值 |
|---|---|---|
| A | 28 | 28 |
| B | 20 | 20 |
| C | 10 | 10 |
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。但是如果在条件中加一句当遇见单位价值相同的时候，优先装重量小的，这样的问题就可以解决。
示例2：钱币找零
假设 1 元、 2 元、 5 元、 10 元、 20 元、 50 元、 100 元的纸币分别有 c0, c1, c2, c3, c4, c5, c6 张。现在要用这些钱来支付 K 元，至少要用多少张纸币？
用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经 事先将Value 按照从小到大的顺序排好。
示例题解（不要用于任何的题目抄袭行为）：
#include<iostream>
#include<algorithm>
using namespace std;
int solve(int money,const vector<pair<int,int>>& moneyCount) {
int num = 0; //首先选择最大面值的纸币
for (int i = moneyCount.size() - 1; i >= 0; i--) {
//需要的当前面值与面值数量取最小
int c = min(money / moneyCount[i].first, moneyCount[i].second);
money = money - c * moneyCount[i].first;
num += c;
}
if (money > 0) num = -1;
return num;
}
贪心与dp的区别
动态规划和贪心算法的区别
动态规划和贪心算法都是一种递推算法 均有局部最优解来推导全局最优解
不同点：
贪心算法：
- 贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
- 由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。
动态规划算法：
- 全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
- 动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
- 边界条件：即最简单的，可以直接得出的局部最优解
贪心算法与动态规划
贪心法的基本思路：
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
- 不能保证求得的最后解是最佳的；
- 不能用来求最大或最小解问题；
- 只能求满足某些约束条件的可行解的范围。实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解
钱币找零的冻动规与贪心的区别
01./**********************************************************
02. *问 题：有最小面额为 11 5 1的三种人民币，用最少的张数找钱
03. *描 述：动态规划与贪心算法 解决问题 比较
04. *作 者：JarvisChu （jiangjunming转载）
05. **********************************************************/
06.#include<stdio.h>
07.#define N 4
08.#define VALUE1 11 //面额为 11元的人民币 （可以修改）
09.#define VALUE2 5 //面额为 5元的人民币 （可以修改）
10.#define VALUE3 1 //面额为 1元的人民币 （不要修改，不然会有找不开的情况）
11.#define MAX_MONEY 1000 //能找开的钱的上限
12.
13./***************************动态规划法********************************
14. *方法：
15. * int Num[MAX_MONEY]; //Num[i]保存要找开 i 元钱，需要的最小人民币张数
16. * int Num_Value[N][MAX_MONEY]; //Num_Value[i][j] 表示 要找 j元钱，需要面额 VALUEi 的人民币张数
17. *
18. * Num[i] = i; 0<= i <=4
19. * Num[i] = min(Num[i-VALUE1]+1,Num[i-VALUE2]+1,Num[i-VALUE3]+1)
20. */
21.
22.//-------------------------求最小值---------------------------------
23.int min(int a,int b,int c){
24. return a<b ? (a<c ? a:c):(b<c ? b:c);
25.}
26.//-------------------------求最优值---------------------------------
27.int DP_Money(int money,int Num[]){
28. //获得要找开money元钱，需要的人民币总张数
29. int i;
30. for(i=0;i<=VALUE2;i++){ //0~4 全用 1元
31. Num[i]=i;
32. }
33. for(i=VALUE2;i<=money;i++){ //从5元开始 凑钱
34. if(i-VALUE1 >= 0){ //如果比 11 元大，说明多了一种用11元面额人民币的可能
35. //从用 11元、5元、1元中 选择一个张数小的
36. Num[i] = min(Num[i-VALUE1]+1,Num[i-VALUE2]+1,Num[i-VALUE3]+1);
37. }
38. else{ //从5元、1元中 选择一个张数小的
39. Num[i] = (Num[i-VALUE2]+1) < (Num[i-VALUE3]+1) ? (Num[i-VALUE2]+1):(Num[i-VALUE3]+1);
40.// Num[i] = min(Num[i-VALUE2]+2,Num[i-VALUE2]+1,Num[i-VALUE3]+1);
41. }
42. }
43. return Num[money];
44.}
45.//-------------------------求最优解---------------------------------
46.void BestChoice(int money,int Num[],int Num_Value[N][MAX_MONEY]){
47. //要找 money 元钱，总人民币张数放在Num[money]中
48. //Num[1~3][money]分别保存三种面额的张数
49. int i;
50. for(i=0;i<VALUE2;i++){
51. Num_Value[1][i] = 0;
52. Num_Value[2][i] = 0;
53. Num_Value[3][i] = i;
54. }
55. for(i=VALUE2;i<=money;i++){
56. if((i>=VALUE1) && (Num[i] == (Num[i-VALUE1]+1))){ //i 是由 i-11+11 构成 即i元是由 i-11元 加上一张面额11元的人民币构成
57. Num_Value[1][i] = Num_Value[1][i-VALUE1]+1; //多一张 11元面额人民币
58. Num_Value[2][i] = Num_Value[2][i-VALUE1]; // 5元面额人民币 张数一样多
59. Num_Value[3][i] = Num_Value[3][i-VALUE1]; // 1元面额人民币 张数一样多
60. }
61. else if(Num[i] == (Num[i-VALUE2]+1)){ //i 是由 i-5+5 构成
62. Num_Value[1][i] = Num_Value[1][i-VALUE2]; //11元面额人民币 张数一样多
63. Num_Value[2][i] = Num_Value[2][i-VALUE2]+1; //多一张 5元面额人民币
64. Num_Value[3][i] = Num_Value[3][i-VALUE2]; // 1元面额人民币 张数一样多
65. }
66. else if(Num[i] == (Num[i-VALUE3]+1)){ //i 是由 i-1+1 构成
67. Num_Value[1][i] = Num_Value[1][i-VALUE3]; //11元面额人民币 张数一样多
68. Num_Value[2][i] = Num_Value[2][i-VALUE3]; // 5元面额人民币 张数一样多
69. Num_Value[3][i] = Num_Value[3][i-VALUE3]+1; //多一张 1元面额人民币
70. }
71. else{
72. }
73. }
74.}
75.
76./***************************贪心算法********************************
77. *方法：
78. * Num_Value[i]表示 面额为VALUEi 的人民币用的张数
79. * 能用大面额的人民币，就尽量用大面额
80. */
81.int Greed(int money,int Num_Value[]){
82. //要找开 money元人民币，Num_Value[1~3]保存 三种面额人民币的张数
83. int total=0; //总张数，返回值也即是总张数。
84. Num_Value[1] = 0;
85. Num_Value[2] = 0;
86. Num_Value[3] = 0;
87. for(int i=money;i>=1;){
88. if(i >= VALUE1){
89. Num_Value[1]++;
90. i -= VALUE1;
91. total++;
92. }
93. else if(i >= VALUE2){
94. Num_Value[2]++;
95. i -= VALUE2;
96. total++;
97. }
98. else if(i >= VALUE3){
99. Num_Value[3]++;
100. i -= VALUE3;
101. total++;
102. }
103. else{
104. }
105. }
106. return total;
107.}
108.void main(){
109. //测试 动态规划法
110./* int i;
111. int money = 23;
112. int Num[MAX_MONEY]; //Num[i]保存要找开 i 元钱，需要的最小人民币张数
113. int Num_Value[N][MAX_MONEY]; //Num_Value[i][j] 表示 要找 j元钱，需要面额 VALUEi 的人民币张数
114. printf("%d\n",DP_Money(money,Num));
115. printf("-------------------------------------------\n");
116. BestChoice(money,Num,Num_Value);
117. printf("-------------------------------------------\n");
118. for(i=0;i<=money;i++){
119. printf("Num[%d]=%4d, %3d, %3d, %3d\n",i,Num[i],Num_Value[1][i],Num_Value[2][i],Num_Value[3][i]);
120. }
121.*/
122.
123. //测试 贪心算法
124./* int i;
125. int Num_Value_Greed[4];
126. for(i=0;i<=40;i++){ //从0 元到 40 元的每一个找钱方式
127. Greed(i,Num_Value_Greed);
128. printf("%d---->>> %d,%d,%d\n",i,Num_Value_Greed[1],Num_Value_Greed[2],Num_Value_Greed[3]);
129. }
130.*/
131.
132. //比较两个算法
133. int i;
134. int dp,grd; //分别保存动态规划法和贪心算法得到的人民币总张数
135. int money; //要找的钱
136. int Num[MAX_MONEY]; //Num[i]保存要找i花费的银币的数目
137. int Num_Value[N][MAX_MONEY]; //Num_Value[i][j] 表示 要找 j 花费的 面值为 VALUEi 的硬币 的数目
138. int Num_Value_Greed[N]; //Num_Value_Greed[i] 表示 面值为VALUEi 的人民币 数目
139. money = 15; //可以为任意非负整型值（15 元是一个比较典型的可以区分两种算法的值）
140. dp = DP_Money(money,Num); //动态规划法
141. BestChoice(money,Num,Num_Value);
142. grd = Greed(money,Num_Value_Greed); //贪心算法
143. printf("要找的钱 为：%d\n\n",money);
144. printf(" 算法 张数 11元 5元 1元\n");
145. printf("动态规划 %-4d %-4d %-3d %-3d\n",dp,Num_Value[1][money],Num_Value[2][money],Num_Value[3][money]);
146. printf("贪心算法 %-4d %-4d %-3d %-3d\n",grd,Num_Value_Greed[1],Num_Value_Greed[2],Num_Value_Greed[3]);
147.}