钱币找零问题
2023-02-18 16:34:30 时间
钱币找零问题
这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元,至少要用多少张纸币?用贪心算法的思想,很显然,每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。
代码:
#include<iostream>
#include<algorithm>
using namespace std;
const int N=7;
int Count[N]={3,0,2,1,0,3,5};//每一张纸币的数量
int Value[N]={1,2,5,10,20,50,100};//每一张的面额
int solve(int money)
{
int num=0;
for(int i=N-1;i>=0;i--)
{
int c=min(money/Value[i],Count[i]);//每一个所需要的张数
money=money-c*Value[i];
num+=c;//总张数
}
if(money>0) num=-1;
return num;
}
int main()
{
int money;
cin>>money;
int res=solve(money);
if(res!=-1) cout<<res<<endl;
else cout<<"NO"<<endl;
}
相关文章
- SpringBoot-技术专区-用正确的姿势如何用外置tomcat配置及运行(Tomcat优化分析)
- 【SpringCloud技术专题】「原生态Fegin」打开Fegin之RPC技术的开端,你会使用原生态的Fegin吗?(下)
- 【SpringCloud技术专题】「原生态Fegin」打开Fegin之RPC技术的开端,你会使用原生态的Fegin吗?(中)
- 【SpringCloud技术专题】「原生态Fegin」打开Fegin之RPC技术的开端,你会使用原生态的Fegin吗?(上)
- 🏆(不要错过!)【CI/CD技术专题】「Jenkins实战系列」(4)jenkins+pipeline构建自动化部署
- 🏆(不要错过!)【CI/CD技术专题】「Jenkins实战系列」(3)Jenkinsfile+DockerFile实现自动部署
- 【Maven实战技巧】「插件使用专题」Maven-Assembly插件实现自定义打包
- [书单]
- MySQL-技术专题-innodb存储引擎
- 浅谈NIO和Epoll的实现原理
- Netty-技术专区-Netty中的buffer
- Redis-技术专区-分布式锁实现
- MySQL-技术专区-详解索引原理
- Netty-技术专区-基础入门介绍
- DNS访问原理就明明白白了
- SpringBoot-技术专区-application配置文件详解
- SpringBoot-技术专区-新特配置文件属性跟踪
- SpringCloud-技术专区-Gateway优雅的处理Filter抛出的异常
- SpringCloud-技术专区-Gateway全局通用异常处理
- Mybatis-技术专区-插件开发指南