题目:
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。 现在要用这些钱来支付K元,至少要用多少张纸币? 用贪心算法的思想, 很显然,每一步尽可能用面值大的纸币即可。 在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。
使用贪心来解决,思路:
从最大值100元开始计算,根据自己现有的对应金钱的票数进行取最小值
例如:现有有500元,但是你100元只有四张,对于100能够约分得到5,但是实际剩余只有4张,所以两者取最小值,并且根据每次求出的减去在进行运算,得出最后money是否为0,如果是那么就够,不是说明不能
#include <iostream> #include <cstdio> #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}; //若是能够合理得到那么就会返回张数,否则返回-1 int count_Money(int money) { int num=0; for(int i=N-1;i>=0;i--){ int c = min(money/Value[i],Count[i]); //min用来比较当前钱数能约分几张与剩余张数进行求最小值 money = money-c*Value[i]; if(c!=0) cout<<Value[i]<<"元:"<<c<<"张"<<endl; num = num+c; } if(money==0) return num; else return -1; } int main() { int money; scanf("%d",&money); int ret = count_Money(money); if(ret==-1) cout<<"don't change!"; else cout<<ret<<endl; return 0; }