【算法】硬币找钱问题（贪心算法）_设有6 种不同面值的硬币,各硬币的面值分别为5 分,1 角,2 角,5 角,1 元,2元。现要

设有6 种不同面值的硬币，各硬币的面值分别为5 分，1 角，2 角，5 角，1 元，2元。现要用这些面值的硬币来购物。在购物中希望使用最少个数硬币。例如，1 次购物需要付款0.55 元，如果没有5 角的硬币，只好用2x2角+1x1角+1x5分 共4 枚硬币来付款。

对于给定的各种面值的硬币个数和付款金额，计算使用硬币个数最少的交易方案。

输入格式:
输入数据有若干组，第一行给出一个整数n表示输入数据的组数。

以下n行每一行有6 个整数和1个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。

输出格式:
输出每组数据的最少硬币个数。如果不可能完成交易，则输出“impossible”。

输入样例:

2
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55

输出样例:

4
4

问题分析
将数字乘以100，方便计算
用数组a【6】={5，10，20，50，100，200}，存入钱的面值
b【6】表示每种硬币的个数
如果要最少的硬币个数，则从面值最大的开始找钱，当付款金额小于该面值时，i+1，找下一个，每找到一个；总钱数减去该面值，计数加1，b【i】减1；直到钱数等于0；如果减完的金额不小于0，则不可能完成交易，则输出“impossible”。

注意：因为是double类型，和真实数据存在误差，所以在判断最后金额的时候，两个数无限接近的时候用1e-7来近似看作等于0，只要金额小于等于1e-7，则可以完成交易。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int a[6]={5,10,20,50,100,200};
    int b[6];
    int n;
    cin>>n;//输入n组数据
    while(n--){
        int j;
        for(j=0;j<6;j++){
            cin>>b[j];
        }
        double money;
        cin>>money;
        money=money*100;
        int num=0;
        for(j=5;j>=0;j--)
        {
            if(money>=a[j]&&b[j]>0){
                money=money-a[j];
                b[j]--;
                j++;
                num++;
            }
        }
        if(money<=1e-7){
            cout<<num<<endl;
        }
        else{
            cout<<"impossible"<<endl;
        }

    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40