贪心算法初步理解找零钱问题_贪心法找零问题

何为贪心算法

贪心算法分为三步

1. 划分区间
2. 由最大给定条件开始 逆推出每个区间内的最优解
3. 各个最优解相加

应用

找零问题

• 条件：整钱换零钱。 输入给定的钱数，元为单位，输出最小的人民币支出形式。例如：输入34.12元，输出20元1张、10元1张、1元4张、1角1张、1分2张
• 碍于输出问题 我们将面值均扩大100倍进行代码编写。

#include <stdio.h>
double change(double money )
{
	int i2000, i1000, i100, i10, i1;
	double mc = money * 100;
	double r=0;
	for (i2000 = 0; i2000 <= mc / 2000; i2000++)//求20面值最优解 以下循环同理
	{
		r = mc - i2000 * 2000 ;
		if (r < 2000)
			break;
	}
	for (i1000 = 0; i1000 <= mc / 1000; i1000++)
	{
		r = mc - i2000 * 2000 - i1000 * 1000;
		if (r < 1000)
			break;
	}
	for (i100 = 0; i100 <= mc / 100; i100++)
	{
		r = mc - i2000 * 2000 - i1000 * 1000 - i100 * 100;
		if (r < 100)
			break;
	}
	for (i10 = 0; i10 <= mc / 10; i10++)
	{
		r = mc - i2000 * 2000 - i1000 * 1000 - i100 * 100 - i10 * 10;
		if (r < 10)
			break;
	}
	for (i1 = 0; i1<= mc / 1; i1++)
	{
		r = mc - i2000 * 2000 - i1000 * 1000 - i100 * 100 - i10 * 10 - i1 * 1;
		if (r < 0)
			break;
	}

			printf("20块钱%d张，10块钱%d张,1块钱%d张,1角钱%d张,1分钱%d张", i2000, i1000, i100, i10, i1);//各面值找零次数
			return 0;
}
int main()
{
	change(34.12);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46