贪婪算法_换零钱(C语言)

╰半夏微凉° 2021-11-23 06:16 312阅读 0赞

贪婪算法思路：  
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到算法种的某一步不能继续前进时，就停止算法，给出近似解。  
由贪婪算法的特点和思路可看出，该算法存在以下问题：  
(1)不能保证最后的解是最优的；  
(2)不能用来求最大或最小解问题；  
(3)只能求满足某些约束条件的可行解的范围。

实例：换零钱  
人民币有100、50、10、5、2、1、0.5、0.2、0.1等多种面额。在找零钱的时候，会有多种方案，例如需找零钱68.90元，至少有以下方案：  
(1)1张50、1张10、1张5、3张1、1张0.5、2张0.2  
(2)1张50、1张10、1张5、3张1、1张0.5、4张0.1  
(3)6张10、1张5、3张1、1张0.5、2张0.2

C语言相关代码

#include<stdio.h>
    #define MAX 9 
    int exchange(int n);
    int price[MAX]={10000,5000,1000,500,200,100,50,20,10};
    int num[MAX]={0};
    int exchange(int n)
    {
    	int i,j;
    	
    	for(i=0;i<MAX;i++)
    	{
    		if(n>price[i])//找到比n小的最大面额 
    		break;
    	}
    	while(n>0 && i<MAX)
    	{
    		if(n>=price[i])
    		{
    			n-=price[i];
    			num[i]++;  //这一类面额的人民币需要几张 
    		}else if(n<10 && n>=5) //不足一毛的 
    		{
    			num[MAX-1]++;
    			break;
    		}else i++;
    	}
    	return 0;
    }
    int main()
    {
    	int i;
    	float m;
    	printf("请输入找零的金额：");
    	scanf("%f",&m);
    	exchange((int)100*m);
    	printf("\n%.2f元零钱的组成：\n",m);
    	for(i-0;i<MAX;i++)
    	{
    		if(num[i]>0)
    			printf("%6.2f:%d张\n",(float)price[i]/100.0,num[i]);
    	 } 
    	 return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，312人围观）

还没有评论，来说两句吧...

相关阅读

相关贪心算法(贪婪算法)

贪心算法(贪婪算法) 文章目录 \\贪心算法思想\\ 选择排序平衡字符串买卖股票

一时失言乱红尘/ 2023年10月04日 18:35/ 0 赞/ 47 阅读

相关贪婪算法——换零钱

算法思路从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到算法中某一步不能不能再继续前进时，就停止算法，给出近似值。 ----

不念不忘少年蓝@/ 2022年09月06日 10:29/ 0 赞/ 187 阅读

相关 C语言贪心算法，关于零钱取整问题

include<stdio.h> void greedyMoney(int m[],int k,int n); int main(void) {

╰+哭是因爲堅強的太久メ/ 2022年08月19日 12:12/ 0 赞/ 155 阅读

相关换零钱--动态规划

题目示例：【题目】给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有

矫情吗；*/ 2022年08月18日 01:59/ 0 赞/ 156 阅读

相关动态规划题目（一）——换零钱

动态规划题目（一）——换零钱 1. 题目描述想兑换100元钱，有1,2,5,10四种钱，问总共有多少兑换方法。下面提供两种实现

布满荆棘的人生/ 2022年08月06日 01:07/ 0 赞/ 173 阅读

相关 C语言贪心算法之贪婪的老鼠

Greedy Mouse 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述 A fat mouse prepared M poun

忘是亡心i/ 2022年06月02日 07:24/ 0 赞/ 214 阅读

相关贪婪算法

贪婪算法贪婪算法(Greedy Algorithm)也叫算贪心法,贪婪法.它是一个遵循启发式解决问题的算法范式.它的核心思想就是通过在每一步的选择中都选用当前步骤下最优

左手的ㄟ右手/ 2022年04月27日 20:40/ 0 赞/ 268 阅读

相关贪婪算法_换零钱(C语言)

贪婪算法思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到算法种的某一步不能继续前进时，就停止算法，给出近似解。由贪婪算法的特点和思

╰半夏微凉°/ 2021年11月23日 06:16/ 0 赞/ 313 阅读

相关贪婪算法

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所

小灰灰/ 2021年11月17日 12:02/ 0 赞/ 319 阅读

相关 C++数据结构与算法（贪婪算法）

> 贪婪算法（Greedy Method）也称贪心算法，在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦做出，就不可再

谁借莪１个温暖的怀抱￠/ 2021年11月10日 10:44/ 0 赞/ 397 阅读