钱币找零问题

待我称王封你为后i 2022-06-18 04:20 220阅读 0赞

钱币找零问题  
这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  \#include<iostream>
2.  \#include<algorithm>
3.  **using****namespace** std; 
4.  **const****int** N=7; 
5.  **int** Count\[N\]=\{3,0,2,1,0,3,5\}; 
6.  **int** Value\[N\]=\{1,2,5,10,20,50,100\}; 
7.  
8.  **int** solve(**int** money) 
9.  \{ 
10. **int** num=0; 
11. **for**(**int** i=N-1;i>=0;i--) 
12.  \{ 
13. **int** c=min(money/Value\[i\],Count\[i\]); 
14.  money=money-c\*Value\[i\]; 
15.  num+=c; 
16.  \} 
17. **if**(money>0) num=-1; 
18. **return** num; 
19. \} 
20. 
21. **int** main() 
22. \{ 
23. **int** money; 
24.  cin>>money; 
25. **int** res=solve(money); 
26. **if**(res!=-1) cout<<res<<endl; 
27. **else** cout<<"NO"<<endl; 
28. \}

[view plain]: http://blog.csdn.net/qq_32400847/article/details/51336300#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/1676578
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/1676578/fork

发表评论取消回复

表情：

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

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

相关阅读

相关钱币兑换问题（完全背包）

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

￡神魔★判官ぃ/ 2022年08月02日 14:53/ 0 赞/ 163 阅读

相关钱币兑换问题（母函数）

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

超、凢脫俗/ 2022年08月02日 14:52/ 0 赞/ 173 阅读

相关钱币找零问题

钱币找零问题这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6

待我称王封你为后i/ 2022年06月18日 04:20/ 0 赞/ 221 阅读

相关问题 : 最少钱币数

题目描述这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 6 种钱币面值为 2、5、10、20、50、100，用来凑 15 元，

短命女/ 2022年06月10日 03:07/ 0 赞/ 168 阅读

相关 hdu 1284 钱币兑换问题

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

客官°小女子只卖身不卖艺/ 2022年05月31日 09:44/ 0 赞/ 142 阅读

相关贪心算法之钱币找零问题

贪心算法一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上

青旅半醒/ 2022年05月18日 23:59/ 0 赞/ 344 阅读

相关 A - 钱币兑换问题

题目描述：在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768

爱被打了一巴掌/ 2022年03月07日 15:22/ 0 赞/ 165 阅读

相关 G - 钱币兑换问题

题目描述：在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。 Input 每行只有一个正整数N，N小于32768

我不是女神ヾ/ 2022年02月24日 06:52/ 0 赞/ 226 阅读

相关贪心算法 - 钱币找零问题

这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱

深藏阁楼爱情的钟/ 2022年02月21日 07:10/ 0 赞/ 218 阅读

相关 HDU 1284 钱币兑换问题

include<cstdio> include<cstring> include<cmath> include<algorithm> u

落日映苍穹つ/ 2021年12月22日 11:39/ 0 赞/ 149 阅读