找零钱问题——贪心算法

蓝桥杯——算法训练——找零钱

有n个人正在饭堂排队买海北鸡饭。每份海北鸡饭要25元。奇怪的是，每个人手里只有一张钞票（每张钞票的面值为25、50、100元），而且饭堂阿姨一开始没有任何零钱。请问饭堂阿姨能否给所有人找零（假设饭堂阿姨足够聪明）
输入格式

第一行一个整数n，表示排队的人数。
接下来n个整数a[1],a[2],…,a[n]。a[i]表示第i位学生手里钞票的价值（i越小，在队伍里越靠前）

输出格式输出YES或者NO

样例输入_0

4
25 25 50 50

样例输出_0

YES

样例输入_1

2
25 100

样例输出_1

NO

样例输入_2

4
25 25 50 100

样例输出_2

YES

数据规模和约定
n不超过1000000
———————————————————————————————————————
思路分析：这道题的关键就是在模拟时贪一把（从大面额开始），基本思路主要在代码注释里，这里强调注意输出形式，一定要区分大小写。

#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>
using namespace std;
int a[1000005];
int main(){int n;while(scanf("%d", &n) != EOF){memset(a, 0, sizeof(a));//把a个内存单元为a的设置初始值为0for(int i=0; i<n; i++) scanf("%d", &a[i]);//输入一个数，代表同学给阿姨的钱int m_25 = 0, m_50 = 0, m_100 = 0; // 分别用来存储阿姨手中不同面额纸币的数量，一开始的时候，阿姨手中的25 元，50元，100元的钞票都为0if(a[0] != 25)//如果其中一个同学一开始给的不是25，那么阿姨此时没得找，返回noprintf("NO\n"); // 这一点需要注意，由于阿姨手里一开始没有零钱，所以如果第一个人就给50，直接ggelse{m_25++; // 先拿一张25再说，25不需要找零bool flag = true; // bool值用来动态表示阿姨能否找回零钱，素衣阿姨可以支付，就是找回零钱for(int i=1 ;i<n; i++){// 阿姨收到钱首先会自动成为她的零钱库if(a[i] == 25) m_25++;//支付宝到账25元else if(a[i] == 50) m_50++;//支付宝到账50元else m_100++;//支付宝到账100元// 每一个人付的钱首先要减去25，余值才是阿姨需要找回的零钱额，这一点必须注意a[i] -= 25;//这个操作是上面三个情况都需要执行的操作，减去大盘鸡本身的价格25元，剩下的就是要找回的钱数// 三个while循环的顺序就是贪心策略的体现while(a[i] > 100 && m_100){a[i] -= 100;m_100--;//找零钱之后，阿姨手中的钞票要减少}while(a[i] > 50 && m_50){a[i] -= 50;m_50--;}while(a[i] > 0 && m_25){a[i] -= 25;m_25--;}if(a[i]){ // 如果应找零钱额不为0flag = false;break;}}if(flag) printf("YES\n");else printf("NO\n");}}return 0;
}

——————————————————————
给定了6种钱币面值为2、5、10、20、50、100，
用来凑 15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。
显然，最少需要2个钱币才能凑成15元。
你的任务就是，

给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。

我再说说我之前是怎么想的吧，我是想应该先从最大币值来依次找零，其实有时又要递归回去再判断，很麻烦的。

举个例子：31吧，从比不大于31的零钱来找零的过程是，36-20=16,16-10=6，6-5=1，到这发现没有零钱比这小了，所以得递归回去，1+5=6，因为刚刚减5行不通，所以得递推到上一步，那就往下一个小值找，那就是6-2=4,4-2=2,2-2=0这样找找到最小找零纸币数了。

这个过程可以用代码描述出来，我就是觉得麻烦，刚看到枚举还是很好接受的。

代码仅供参考，以后想到好方法会补上来。

#include<stdio.h> int main() { int a,b,c,d,e,f; int money; printf(“请输入所要找零的钱:”); scanf("%d",&money); int s=money/2+1;
//这个s初值为最多纸币数 int t=s; for(a=0;a<=money/2+1;a++) {
for(b=0;b<=money/5+1;b++) { for(c=0;c<=money/10+1;c++) {
for(d=0;d<=money/20+1;d++) { for(e=0;e<=money/50+1;e++) {
for(f=0;f<=money/100+1;f++) {
if(f100+e50+d20+c10+b5+a2= =money){
//printf("%d-%d-%d-%d-%d-%d\n",f,e,d,c,b,a); if(a+b+c+d+e+f<s)
s=a+b+c+d+e+f;
}
}
} } } } } if(s==t) printf(“找不到对应的零钱\n”); else printf(“所需最小纸币数为：%d\n”,s); return 0; }

程序大致流程：输入总额，输入最少找零纸币数。如果不能找到，则输入提示信息。
——————————————————————————
有n个人正在饭堂排队买海北鸡饭。每份海北鸡饭要25元。奇怪的是，每个人手里只有一张钞票（每张钞票的面值为25、50、100元），而且饭堂阿姨一开始没有任何零钱。请问饭堂阿姨能否给所有人找零（假设饭堂阿姨足够聪明）
输入格式
解题思路：

可以知道，50元和100元需要找钱，先满足找钱的条件，才能具体的操作找钱。

【1】50元需满足的找钱条件：阿姨口袋中25元钱的个数>=1；

【2】100元需满足的找钱条件：阿姨口袋中25元和50元各一张或者25元钱个数>=3；

【3】25元不需满足找钱条件；

AC代码：

#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int a[1000000];
int main()
{int n,i;int money25=0;//阿姨口袋中25元的个数 int money50=0;//阿姨口袋中50元的个数 int money100=0;//阿姨口袋中100元的个数 cin>>n;for(i=0;i<n;i++)cin>>a[i];int flag=1;//阿姨是否可以给所有人成功找钱 for(i=0;i<n;i++){if(a[i]==50)//第i个人前面必须有一个25元 ，才符合找钱条件 {if(money25>=1)//符合找钱条件 {money25--;money50++; }else{flag=0;//找钱失败 break;}}else if(a[i]==100)//第i个人前面必须有一个25和50元或者3个25元 ，才符合找钱条件 {if(money50>=1&&money25>=1){money50--;money25--;money100++;}else if(money25>=3){money25-=3;money100++;}else{flag=0;//找钱失败 break;}}else//手里拿着的是25元，阿姨不用找钱 money25++;}	if(flag)cout<<"YES"<<endl;elsecout<<"NO"<<endl;return 0;
}

————————————————————————

Java版本

import java.util.*;public class Main {static Scanner sc = new Scanner(System.in);static int danjia = 25;static int xianyoudanjia = 0;public static void main(String[] args) {int n = sc.nextInt();int qian[] = new int[n];for (int i = 0; i < n; i++) {qian[i] = sc.nextInt();}Boolean bool = true; List<Integer> list = new ArrayList<>(); //利用List存放暂时找不开的人，先去一边排队去。//其实这个地方使用队列会更好。为了简便，我就没使用。//找钱for (int i = 0; i < qian.length; i++) {//如果第i个排队的人的钱足够if (qian[i] == danjia) {zongqianshu+= qian[i];//qian[i]>danjia：第i个人有的钱，大于单价，就说明要找钱了//(个人的钱 - 单价)=要找的钱，如果食堂阿姨现有的领钱>=要找的钱，说明可以找开} else if (qian[i] > danjia && ((qian[i] - danjia) <= zongqianshu)) {//找钱，找钱时要记得加上25，然后再减zongqianshu += 25;zongqianshu-= (qian[i] - danjia);//然后减去找去的钱}else{list.add(qian[i]);}}//找刚才没找开的for (int i = 0; i < list.size(); i++) {if(zongqianshu>=list.get(i)){zongqianshu -= list.get(i);list.remove(i); //找完要移除，因为已经找完第i个人了，剩下的就是没找的}else{bool = false;}}System.out.println(list.size()==0?"YES":"NO");//判断是否剩下没找钱的人}
}

人民币的面额有100元、50元、10元、5元、2元、1元等。在找零钱时，可以有很多中方案。例如146的找零方案如下：

（1）100+20+20+5+1
（2）100+20+10+10+5+1
（3）100+20+10+10+2+2+2
（4）100+10+10+10+10+1+1+1+1+1+1

【分析】

利用贪心算法，则选择的是第1种方案，首先选择一张面额最大的人民币，即100元面额的，然后在剩下的46元中选择面额最大的20元。依次选择的都是局部最优解。

code：

#include<stdio.h>
#include <iostream>
#define N 60
int exchage(float n, float *a, int c, float *r);//找零函数
void main()
{float rmb[] = { 100,50,20,10,5,2,1,0.5,0.2,0.1 };//代表人民币面值有这些int n = sizeof(rmb) / sizeof(rmb[0]), k, i;//用输入的需要找零的钱数除以最大的100面值float change, r[N];;//change需要找零的钱数，r【】存放那个需要几个printf("请输入要找的零钱数:");scanf("%f", &change);for (i = 0; i < n; i++)if (change >= rmb[i])//如果要找零的钱大于人民币已有的面值大小break;k = exchage(change, &rmb[i], n - i, r);if (k <= 0)printf("找不开!\n");else{printf("找零钱的方案:%.2f=", change);if (r[0] >= 1.0)printf("%.0f", r[0]);elseprintf("%.2f", r[0]);for (i = 1; i < k; i++){if (r[i] >= 1.0)printf("+%.0f", r[i]);elseprintf("+%.2f", r[i]);}printf("\n");}system("pause");
}
int exchage(float n, float *a, int c, float *r)
{int m;//开始不懂了。。。。。。。？？？？？？？if (n == 0.0)				/*能分解，分解完成*/return 0;if (c == 0)				/*不能分解*/return -1;if (n < *a)return exchage(n, a + 1, c - 1, r);	/*继续寻找合适的面值*/else{*r = *a;					/*将零钱保存到r中*/m = exchage(n - *a, a, c, r + 1);		/*继续分解剩下的零钱*/if (m >= 0)return m + 1;			/*返回找零的零钱张数*/return -1;}
}

————————————————————————
在这里插入图片描述

#include<iostream>
using namespace std;
void find_change(int total_change)
{int Q, D, N, P;Q = D = N = P = 0;//用来计数，分别计算这几种钱需要多少张if ((total_change / 25 > 0) && (total_change > 10))//总的数首先要大于25{Q = total_change / 25;}int total_change_D = total_change % 25;//剩下来的需要找零得数if ((total_change_D / 10 > 0) && (total_change > 5)){D = total_change_D / 10;}int total_change_N = total_change_D % 10;if ((total_change_N / 5 > 0) && (total_change_D > 1)){N = total_change_N / 5;}P = total_change_N % 5;cout << "quarters Q = " << Q << endl;cout << "dimes    D = " << D << endl;cout << "nickles  N = " << N << endl;cout << "pennies  P = " << P << endl;
}//输出者几种钱的张数int main()
{int amount = 0;cout << "Please input the changes you need: " << endl;cin >> amount;find_change(amount);return 0;
}