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

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

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

一、找零钱问题

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

}

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


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【算法】最小重量机器设计

【题目描述】设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设Wij 是 从供应商j处购得的部件i的重量,Cij 是相应的价格。 试设计一个算法,给出总价格不超...

【算法】动态规划(二)——数字三角形问题

【算法】动态规划(二)——数字三角形问题

1.问题描述及状态定义数字三角形问题:有一个非负整数组成的三角形,第一行只有一个数,除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示:从第一行开的数开始走,每次可以往下或右走一格,直到走到...

【算法】最大子段和

【算法】最大子段和

【题目描述】给出一个长度位n的序列a,选出其中连续且非空的一段使得这段和最大【输入描述】第一行是一个整数,表示序列的长度n。第二行有n个整数,第i个整数表示序列的第i个数字ai【输出描述】输出一行一个...

【算法】归并排序

【算法】归并排序

一、基本思想归并排序的核心思想是将两个已经有序的子序列合并成一个有序序列。整个过程分为两个主要步骤: 1.分解:将待排序的序列不断二分,直到每个子序列只包含一个元素(此时自然有序) ...

【DFS】搜索回溯基础

【DFS】搜索回溯基础

0.前言       搜索与回溯是计算机解题中常用的算法,很多问题无法根据某种确定的计算法则来求解,可以利用搜索与回溯的技术求解。...

【贪心】最大子矩阵

【题目描述】已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1X1)子矩阵。比如,如下4 x 4的矩阵0    -2&...