一、找零钱问题

例题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

#include

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

#include

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<

else cout<

}

考虑一下,如果不同面值的钞票数量有限制,能不能直接用贪心算法。

返回目录:算法

上一篇:基本概念

Post Views:

278

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信