大家一起数钢镚

题目描述

Nova君在经历双十一风暴后，不得不靠在一家便利店打工来维持生计。作为一名合格的收银员，必须快速的计算价格并找钱个顾客。Nova君是个十足的硬币控，喜欢金属色闪闪的硬币，所以找钱是都希望用尽可能少的硬币。现在，假设收银台有面值为1元、5元、10元、50元、100元、500元的硬币各Ai、Bi、Ci、Di、Ei、Fi 个，需要找的钱的数额为A元，那最少需要多少个硬币呢？假定至少存在一种找钱方案。

被jhljx附体而不会数数Nova君求助中......

输入

多组测试数据（组数不超过10），对于每组数据，输入两行，第一行为6个正整数，分别代表1元、5元、10元、50元、100元、500元的硬币个数，第二行为一个正整数A，代表需要支付的钱数。所有正整数都在INT范围内。

输出

对于每组数据，输出一行，为最少的硬币数量

输入样例

3 2 1 3 0 2
620

输出样例

6

Hint

放轻松，签到题~
题目来源:http://biancheng.love/contest/23/problem/A/index

解题方法：贪心算法
根据题目需要得到最少的硬币个数（不要问我问什么会有那么大面值的硬币）。考虑一种很实际的问题，比如说你去超市购物，营业员需要找零50元，那么你肯定不希望营业员找给你的钱都是1毛1毛钱。也不想都是1块1块。一般的营业员可能找零50面额的，也可能是10张5元的，或者25张2元的（好久没见过两元纸币了）等等方法。可以看出来找零最少的肯定是直接给一张50元。这就是我们很实际的贪心问题。因此营业员在找零的时候先去拿面值最大的并且小于找零。当满足条件之后，将找零数目减去适合的最大面值，再次进行上述操作，直到找零结束。这样的方法是很实际的贪心问题的应用。
贪心算法的博客推荐：http://www.cnblogs.com/chinazhangjie/archive/2010/11/23/1885330.html
下面给出本题的代码：

#include<iostream>

using namespace std;
int main()
{
    int a[7];
    int b[7]={0,1,5,10,50,100,500};
    int num;
    while(cin>>a[1]){
    int ans=0;
    for(int i=2;i<=6;i++)
        cin>>a[i];
    cin>>num;
    for(int i=6;i>=1;i--)
    {
        while(num-b[i]>=0&&a[i]>0)
        {
            a[i]--;
            ans++;
            num-=b[i];
        }
    }
    cout<<ans<<endl;
    }
}