贪心算法概述
贪心算法
有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量都各不相同。设第i个货箱的重量为wi(1≤i≤n)，而货船的最大载重量为c,我们的目的是在货船上装入最多的货物。这个问题可以作为最优化问题进行描述:设存在一-组变量xi ，其可能取值为0或1。如xi为0，则货箱i将不被装上船;如xi为1,则货箱i将被装.上船。我们的目的是找到一-组xi，使它满足限制条件ni =Zwixi≤c且xi∈[0, 1], 1≤i≤n。相应的优化函数是ni= Zwixi取极值。满足限制条件的每一-组xi都是一 个可行解，能使ni= Zwixi取得极大值的方案是最优解。
贪心算法(也称贪心策略)总是作出在当前看来是最好的选择。但我们看到，可以用动态规划算法来解，其实用贪心算法更简单，更直接且解题效率更高。这利用了问题本身的--些特性。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为:首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。(当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。)
贪心算法的基本思想
贪心算法的基本思想是通过一系列选择步骤来构造问题的解，
每一步都是对当前部分解的一个扩展,直至获得问题的完整解。
所做的每一-步选择都必须满足:
(1) 可行的:必须满足问题的约束。
(2)局部最优:当前所有可能的选择中最佳的局部选择。
(3)不可取消:选择一旦做出， 在后面的步骤中就无法改变了。
例1 删数字问题.
对给定的n位高精度正整数,去掉其中k(k<n)个数字后，按原左右次序将组成一个新的正整数，使得剩下的数字组成的新数最大。
➢操作对象是一个可以超过有效数字位数的n位高精度数,存储在数组a中。
➢每次删除--个数字，选择一个使剩下的数最大的数字作为删除对象。之所以选
择这样“贪心”的操作,是因为删k个数字的全局最优解包含了删一个数字的子
问题的最优解。
➢当k>1(当然小于n),按上述操作一个一个删除。删除一个达到最大后， 再从头
即从串首开始，删除第2个,依此分解为k次完成。
➢若删除不到k个后已无左边小于右边的增序,则停止删除操作，打印剩下串的
左边n-k个数字即可(相当于删除了若干个最右边的数字)。
代码实现
1. #include<stdio.h> 2. 3. void panduan(char* p, int k) 4. { 5. 6. while (k--) 7. { 8. char* s1 = p; 9. while (1)//删除一个数 10. { 11. if (*(s1)-*(s1 + 1) < 0) 12. { 13. char* s2 = s1; 14. while (*s2) 15. { 16. *(s2) = *(s2 + 1); 17. s2++; 18. } 19. break; 20. } 21. s1++; 22. if (!(*s1))//遍历结束后发现最后一位最小 23. { 24. *(s1 - 1) = *s1;//覆盖最后一位 25. break; 26. } 27. } 28. } 29. } 30. 31. int main() 32. { 33. char arr[100]; 34. int k = 0; 35. printf("请输入要删除的数->"); 36. scanf("%s", arr); 37. printf("请选择需要删除的位数->"); 38. scanf("%d", &k); 39. panduan(arr, k); 40. printf("%s", arr); 41. return 0; 42. }
结果展示
例二 背包问题
➢已知n种物品和一一个可容纳c重量的背包，物品的重量为wi,产生的效益为pi。装包
时物品可拆，即可只装每种物品的一部分。显然物品的一部分放入背包可产生的效益为
pi/wi,问如何装包，使所得整体效益最大。
➢(1)算法设计
➢应用贪心算法求解。每一种物品装包，由可以整个装入，也可以只装一部分， 也可以不
装。
➢约束条件:目标函数:要使整体效益即目标函数最大，按单位重量的效益非增次序- -件
件物品装包，直至某-件物品装不下时，装这种物品的一部分把包装满。
示例如下：
代码实现
输入模块
1. printf("请输入物品数->"); 2. scanf("%d", &n); 3. printf("请输入背包容量->"); 4. scanf("%f", &c); 5. printf("请输入每个物品的重量和价值\n"); 6. while (n--) 7. { 8. scanf("%f%f", &wi[i], &pi[i]); 9. i++; 10. }
每件物品的单位价值
1. void danjia(float pj[100], float wi[100], float pi[100], int n) 2. { 3. int i = 0; 4. for (i = 0; i < n; i++) 5. { 6. pj[i] = pi[i] / wi[i]; 7. } 8. }
排序模块
以单位价值进行比较，按降序排列；并且将每个单位价值所对应重量与价值进行排序
1. void paixu(float* p, float* wi, float* pi, int n) 2. { 3. int i = 0; 4. for (i = 0; i < n; i++) 5. { 6. int j = 0; 7. for (j = 0; j < n - 1 - i; j++) 8. { 9. if (*(p + j) < *(p + j + 1)) 10. { 11. float con = *(p + j); 12. *(p + j) = *(p + j + 1); 13. *(p + j + 1) = con; 14. con = *(wi + j); 15. *(wi + j) = *(wi + j + 1); 16. *(wi + j + 1) = con; 17. con = *(pi + j); 18. *(pi + j) = *(pi + j + 1); 19. *(pi + j + 1) = con; 20. } 21. } 22. } 23. }
装包模块
装包需要进行相应判断，判断是否可以全部装入；并做出判断后的相应操作
1. void zhuangbao(float* pj, float* wi, float* pi, int n, int c) 2. { 3. int i = 0; 4. int h = 0; 5. float b = 0; 6. int j = 0; 7. int coun = 0; 8. for (i = 0; (i < n)&&(h < c); i++) 9. { 10. h = h + *(wi + i); 11. } 12. if (h > c) 13. { 14. h = h - *(wi + i); 15. b = (c - h) / *(pj + i); 16. coun = 1; 17. } 18. for (j = 0; j < i-1; j++) 19. { 20. printf("重量为%.2f价值为%.2f 全装\n", *(wi + j), *(pi + j)); 21. } 22. if (coun) 23. { 24. printf("重量为%.2f价值为%.2f 装%.2f\n", *(wi + j), *(pi + j), b); 25. } 26. }
完整代码实现
1. #include <stdio.h> 2. 3. void zhuangbao(float* pj, float* wi, float* pi, int n, int c) 4. { 5. int i = 0; 6. int h = 0; 7. float b = 0; 8. int j = 0; 9. int coun = 0; 10. for (i = 0; (i < n)&&(h < c); i++) 11. { 12. h = h + *(wi + i); 13. } 14. if (h > c) 15. { 16. h = h - *(wi + i); 17. b = (c - h) / *(pj + i); 18. coun = 1; 19. } 20. for (j = 0; j < i-1; j++) 21. { 22. printf("重量为%.2f价值为%.2f 全装\n", *(wi + j), *(pi + j)); 23. } 24. if (coun) 25. { 26. printf("重量为%.2f价值为%.2f 装%.2f\n", *(wi + j), *(pi + j), b); 27. } 28. } 29. 30. void paixu(float* p, float* wi, float* pi, int n) 31. { 32. int i = 0; 33. for (i = 0; i < n; i++) 34. { 35. int j = 0; 36. for (j = 0; j < n - 1 - i; j++) 37. { 38. if (*(p + j) < *(p + j + 1)) 39. { 40. float con = *(p + j); 41. *(p + j) = *(p + j + 1); 42. *(p + j + 1) = con; 43. con = *(wi + j); 44. *(wi + j) = *(wi + j + 1); 45. *(wi + j + 1) = con; 46. con = *(pi + j); 47. *(pi + j) = *(pi + j + 1); 48. *(pi + j + 1) = con; 49. } 50. } 51. } 52. } 53. 54. void danjia(float pj[100], float wi[100], float pi[100], int n) 55. { 56. int i = 0; 57. for (i = 0; i < n; i++) 58. { 59. pj[i] = pi[i] / wi[i]; 60. } 61. } 62. 63. int main() 64. { 65. int n = 0; 66. float c = 0; 67. int i = 0; 68. float wi[100]; 69. float pi[100]; 70. float pj[100]; 71. printf("请输入物品数->"); 72. scanf("%d", &n); 73. printf("请输入背包容量->"); 74. scanf("%f", &c); 75. printf("请输入每个物品的重量和价值\n"); 76. while (n--) 77. { 78. scanf("%f%f", &wi[i], &pi[i]); 79. i++; 80. } 81. danjia(pj, wi, pi, i); 82. paixu(pj, wi, pi, i); 83. zhuangbao(pj, wi, pi, i, c); 84. 85. return 0; 86. }
练习
练习一 快乐司机
输入输出格式
练习二 排队打水问题
输入与输出样例
练习三 盾神与积木游戏
输入与输出格式
这些练习博主就不带大家做了，大家可以根据自己的实际情况进行适度练习。
总结
博主也是第一次参加这种比赛，博文所讲内容为博主参加学校培训所学和博主自己的一些感悟，有讲解不到位或者有错误的地方，欢迎在评论区留言或者私信博主，关于练习题的代码，也可以私信博主，但是我还是希望大家可以自己动手试一试；如果看到这里，就请给博主一个三连吧！
