贪心算法1

2024-06-29 17:43| 来源: 网络整理| 查看: 265

贪心算法是一种不追求最优解，只希望找到较为满意解的方法。贪心算法省去了为找最优解要穷尽所有可能而必须耗费的大量时间，因此它一般可以快速得到比较满意的解。贪心算法常以当前情况做最优选择，而不考虑各种可能的情况没所以贪心算法不需要回溯。

找零钱问题

人民币的面额有100元、50元、10元、5元、2元、1元等。在找零钱时，可以有很多中方案。例如146的找零方案如下：

（1）100+20+20+5+1 （2）100+20+10+10+5+1 （3）100+20+10+10+2+2+2 （4）100+10+10+10+10+1+1+1+1+1+1

【分析】

利用贪心算法，则选择的是第1种方案，首先选择一张面额最大的人民币，即100元面额的，然后在剩下的46元中选择面额最大的20元。依次选择的都是局部最优解。

code：

#include #include #define N 60 int exchage(float n, float *a, int c, float *r); void main() { float rmb[] = { 100,50,20,10,5,2,1,0.5,0.2,0.1 }; int n = sizeof(rmb) / sizeof(rmb[0]), k, i; float change, r[N];; printf("请输入要找的零钱数:"); scanf("%f", &change); for (i = 0; i < n; i++) if (change >= rmb[i]) break; k = exchage(change, &rmb[i], n - i, r); if (k = 1.0) printf("%.0f", r[0]); else printf("%.2f", r[0]); for (i = 1; i < k; i++) { if (r[i] >= 1.0) printf("+%.0f", r[i]); else printf("+%.2f", r[i]); } printf("\n"); } system("pause"); } int exchage(float n, float *a, int c, float *r) { int m; if (n == 0.0) /*能分解，分解完成*/ return 0; if (c == 0) /*不能分解*/ return -1; if (n < *a) return exchage(n, a + 1, c - 1, r); /*继续寻找合适的面值*/ else { *r = *a; /*将零钱保存到r中*/ m = exchage(n - *a, a, c, r + 1); /*继续分解剩下的零钱*/ if (m >= 0) return m + 1; /*返回找零的零钱张数*/ return -1; } }

结果：

【本文地址】

公司简介

联系我们