贪心算法-付钱问题(C语言实现)
2021/10/31 9:39:42
本文主要是介绍贪心算法-付钱问题(C语言实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题
小明是一名程序员,在某个电脑店购买了一把机械键盘,机械键盘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("贪心算法给出了一个最优解"); }
完整代码
#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张\r\n",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("\r\n\r\n"); } return 0; }
这篇关于贪心算法-付钱问题(C语言实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding