贪心算法-付钱问题(C语言实现)_HONKER

问题

小明是一名程序员，在某个电脑店购买了一把机械键盘，机械键盘386元，问，如果支付现金，如何让超市不找钱(若小明有面值为100，50，20，10，5，1元面值的人民币)

贪心算法 为了问题会给出最优解的算法
我们定义一个Info的类型存储钱的信息 一个存储面值 一个存储面值对应的数量
将Info对象初始化 实现了对应的接口 InitInfo
提供下列两个方法 实现数据的遍历
void ForEachInfo(void(cf)(int,int),Info g_info,int size)
void printTwoNumber;

算法实现

Money为要付的钱数 s_info为要设置的信息结构体对象,Size是面值数组的大小
我们为变量Key开辟一个空间 存储当前最大可以用多少钱的人民币付钱
假如钱数大于当前最大值 可以用一张最大面值的人民币 相应的 Quantity对应的数字也要+1
如果小于 则Key查找下一个符合条件的人民币
若Money=186
Key初始为0
Money>100
100元人民币的数量+1
Money-=100
Money为86
此时Money<100,Key+1
当Key=1时,对应的面值为50
Money>50
59元人民币的数量+1
如此往复
可以得到
这些面值的纸币各一张
既1+5+10+20+50+100=186

void Optimal(int Money,Info* s_info,int Size){
	int Key = 0 ; //索引
	if(Money<=0){puts("贪心算法给出了一个最优解");return;}
	while(Money>0&&Key<Size){
		if(Money >= s_info->ParValue[Key]){
			Money -= s_info->ParValue[Key];
			s_info->Quantity[Key]=s_info->Quantity[Key]+1;
			continue;
		}
		Key+=1;
	}
	puts("贪心算法给出了一个最优解");
}
1
2
3
4
5
6
7
8
9
10
11
12
13

完整代码

#include <stdio.h>
#include <stdlib.h>
#define foreach for(;;)
// 2021 - 10 - 31 
struct Info {
	int* ParValue; // 存储面值
	int* Quantity; // 存储数量
};
typedef struct Info Info; 
void InitInfo(int* ParValues,int size,Info* s_info){
	int i=0;
	s_info->ParValue=ParValues;
	s_info->Quantity = (int*)(malloc(sizeof(int)*size));
	while(i<size){
		s_info->Quantity[i]=0;
		i++;
	}
}
void ForEachInfo(void(*cf)(int,int),Info* g_info,int size){
	int i=0;
	while(i<size){
		cf(g_info->ParValue[i],g_info->Quantity[i]);
		i++;
	}
}
void printTwoNumber(int n1,int n2){
	printf("面值为%%d的人民币%%d张
",n1,n2);
}
void Optimal(int Money,Info* s_info,int Size){
	int Key = 0 ; //索引
	if(Money<=0){puts("贪心算法给出了一个最优解");return;}
	while(Money>0&&Key<Size){
		if(Money >= s_info->ParValue[Key]){
			Money -= s_info->ParValue[Key];
			s_info->Quantity[Key]=s_info->Quantity[Key]+1;
			continue;
		}
		Key+=1;
	}
	puts("贪心算法给出了一个最优解");
}
void ClearInfoQuantity(Info* inf,int size){
	int i=0;
	while(i<size){
		inf->Quantity[i]=0;
		i++;
	}
}
int main(int agrc , char* argv[]){
	Info info;
	int arr[] = {100,50,20,10,5,1};// 硬币的面值
	int input;
	InitInfo(arr,sizeof(arr)/sizeof(int),&info);
	foreach{
		   ClearInfoQuantity(&info,sizeof(arr)/sizeof(int));
	       printf("输入要兑换的人民币数量(元):");
		   scanf("%%d",&input);
	       Optimal(input,&info,sizeof(arr)/sizeof(int));
	       ForEachInfo(printTwoNumber,&info,sizeof(arr)/sizeof(int));
		   printf("

");
	}
	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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63