当前位置：首页 > 算法 > 正文内容

【贪心】----找零钱问题

亿万年的星光5年前 (2021-01-28)算法21000

一、找零钱问题

例题1：
有 1 元，5元，10元，20元，100元，200元的钞票无穷多张。现在使用这些钞票支付X元，最少需要多少张钞票。

X = 628

最佳支付方法：

3张200块的，1张20块的，1张5块的，3张1块的

共需3+1+1+3 = 8张
直觉告诉我们:尽可能多的使用面值较大的钞票!
贪心法: 遵循某种规律，不断贪心的选取当前最优策略的算法设计方法。

分析：面额为1元、5元、10元、20元、100元、200元，任意面额是比自己小的面额的倍数关系。所以当使用一张较大面额钞票时，若用较小面额钞票替换，一定需要更多的其他面额的钞票!

代码实现：

#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    const int RMB[]= {200,100,20,10,5,1};
    const int NUM = 6;//6种面值
    int X = 628;
    int count = 0;
    for(int i= 0;i< NUM;i++){
        int use = X / RMB[i];需要面额为RMB[i]的use张
        count + = use；
        X = X -RMB[i] * use;
        printf("需要面额为%d 的%d张",RMB[i],use);
        printf("剩余需要支付金额%d.\n",X);
    }
    printf("总共需要%d张\n",count);
    return 0;
}

为何这么做一定是对的？

面额为 1元，5元，10元，20元，100元，200元，任意面额是比自己小的面额的倍数关系。

所以当使用一张较大面额钞票时，若使用较小面额钞票替换，一定需要更多的其他面额的钞票。

例如：

5=1+1+1+1+1

10=5+5

20=10+10

100=20+20+20+20+20

200=100+100

故：当前最优解即为全局最优解，贪心成立。

例题2：
有1元，5元，6元的纸币，现在用这些钞票支付K元，至少多少张纸币？

经我们分析，这种情况是不适合用贪心算法的，因为我们上面提供的贪心策略不是最优解。比如，要支付10元的话，按照上面的算法，至少需要1张6元的，4张1元的，而实际上最优的应该是2张5元的。

例题3：假设1元、2元、5元、10元、20元、50元、100元的纸币分别有a,b,c,d,e,f,g张。现在要用这些钱来支付m元，至少要用多少张纸币？如果能支付输出最少支付的张数，如果不能支付，输出-1。

#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<<"-1"<<endl;     return 0; 
}