第十六题:

2586:Exact Change Only

题目链接：

P2586——Exact Change Only——柒行（www.oj7.cn）

题目来源：

Waterloo local 2000.01.29

题目描述

总时间限制:

1000ms

内存限制:

65536kB

描述

Boudreaux reached over and shook awake Thibodeaux, who had dozed off somewhere in New Mexico. "Where we at?" Thibodeaux groggily yawned.

"Not in Vegas, I gua-ran-tee, but could you get my knapsack?" Boudreaux asked, gesturing to the worn, leather backpack in the back seat of their cherry red Ford Miata.

"Why, is there a problem?"

"Just hand me my knapsack, problem or not."

Thibodeaux complied, glancing up as Boudreaux slowed the car to a stop in a line of vehicles approaching a toll booth. "$1.65 -- Exact change only," Thibodeaux read the yellow sign on the front of a small wooden building occupied by a lone toll booth operator. "I have to get $1.65 in exact change?" Thibodeaux asked, digging through the knapsack, "all I have are ten quarters, four dimes, and three pennies. I don't have any nickels . . ."

"Just give me five of the quarters and the four dimes," Boudreaux replied, holding out his hand.

"Oh yeah," Thibodeaux said, handing over the coins, "that does add up to $1.65. I wish there were an easy way to figure out if you have an exact monetary amount, given a set of coins."

"Hmmm," Boudreaux shrugged, "sounds like a good programming problem."

输入

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 1 component:

Start line - A single line: A B C D E

where: A: (0.01 <= A <= 5.00) is a decimal number (to two decimal places) of a monetary amount. B: (0 <= B <= 100) is an integer number of quarters (one quarter = $0.25). C: (0 <= C <= 100) is an integer number of dimes (one dime = $0.10). D: (0 <= D <= 100) is an integer number of nickels (one nickel = $0.05). E: (0 <= E <= 100) is an integer number of pennies (one penny = $0.01).

输出

For each data set, there will be exactly one line of output. If there exists one or more subsets of the given coins whose values add up to the given monetary amount exactly, the output will be a single line in the form:

A B C D

where A is the number of quarters, B is the number of dimes, C is the number of nickels, and D is the number of pennies, for the subset with the fewest number of coins. Otherwise, the output will be a single line with the statement: NO EXACT CHANGE

输入数据

0.45 2 1 1 4
0.75 3 7 1 75

输出数据

NO EXACT CHANGE
3 0 0 0

中文题面：

描述

布德罗伸手过去，摇醒了在新墨西哥某处打瞌睡的蒂博多。“我们在哪儿？”蒂博多迷迷糊糊地打着哈欠问道。 “肯定不在拉斯维加斯，我敢打包票，但你能把我背包拿过来吗？”布德罗指着他们那辆樱桃红色福特米亚塔后座上那个磨损的皮质背包说。 “怎么了，出问题了吗？” “先把我的背包给我，不管有没有问题。” 蒂博多照做了，就在布德罗把车在一排靠近收费站的车辆中缓缓停下时，他抬头看了一眼。“$1.65$美元——仅限精确找零”，蒂博多读着一座小木屋前黄色标志牌上的字，木屋里只有一名收费员。“我得有$1.65$美元的精确零钱？”蒂博多一边翻找背包一边问，“我就只有十个$25$美分硬币、四个$10$美分硬币和三个$1$美分硬币。我没有$5$美分硬币……” “那就给我五个$25$美分硬币和四个$10$美分硬币吧。”布德罗伸出手说。 “哦，对哦。”蒂博多说着递过硬币，“确实能凑成$1.65$美元。真希望能有个简单的方法来判断给定一堆硬币时，是否能凑出某个确切金额。” “嗯哼。”布德罗耸耸肩，“听起来像是个不错的编程问题。”

输入

这个问题的输入将由一系列（非空）数据集组成，最多可包含$100$个数据集。每个数据集将按照以下描述格式化，且各数据集之间没有空行分隔。 一个数据集包含$1$个部分： 起始行 - 单行内容： $A B C D E$ 其中： $A$: $(0.01 <= A <= 5.00)$ 是一个保留两位小数的货币金额。 $B$: $(0 <= B <= 100)$ 是四舍五入到整数的$25$美分硬币数量 （一枚25美分硬币= $0.25$美元）。 $C$: $(0 <= C <= 100)$ 是四舍五入到整数的$10$美分硬币数量 （一枚$10$美分硬币= $0.10$美元）。 $D$: $(0 <= D <= 100)$ 是四舍五入到整数的$5$美分硬币数量（一枚$5$美分硬币= $0.05$美元）。 $E$: $(0 <= E <= 100)$ 是四舍五入到整数的$1$美分硬币数量 （一枚$1$美分硬币= $0.01$美元）。

输出

对于每个数据集，将恰好输出一行结果。如果存在一个或多个给定硬币子集的值恰好能加起来等于给定的货币金额，则输出格式为： $A B C D$ 其中$A$是$25$美分硬币的数量，$B$是$10$美分硬币的数量，$C$是$5$美分硬币的数量，$D$是$1$美分硬币的数量，对应于所需硬币数量最少的子集。否则，输出将为一行内容：“NO EXACT CHANGE”。

输入数据1

0.45 2 1 1 4
0.75 3 7 1 75

输出数据1

NO EXACT CHANGE
3 0 0 0

算法标签

贪心算法 穷举

解题思路：

读取输入数据，将货币金额转换为以美分为单位的整数表示，方便后续计算。通过嵌套循环枚举所有从最大面值到最小面值可能的硬币组合，对于每一种组合，检查其总值是否等于目标金额，并记录最小的硬币总数。如果找到符合条件的组合，则输出该组合；否则输出“NO EXACT CHANGE”。

实现步骤：

输入读取：

一直读取每组数据直到没有读取五个值（表示输入完成）

数据初始化：

将金额 $A$ 转换为以分为单位的整数。初始化 $min$ 为最大整数值，用于记录最少硬币数

25美分硬币：

计算最多可以使用的$25$美分硬币数量，并确定实际可用的最大值。遍历所有可能的$25$美分硬币数量 $a$，计算剩余金额。如果剩余金额小于$0$，跳过当前循环。

10美分硬币：

计算最多可以使用的$10$美分硬币数量，并确定实际可用的最大值。遍历所有可能的$25$美分硬币数量 $a$，计算剩余金额。如果剩余金额小于$0$，跳过当前循环。

5美分硬币：

计算最多可以使用的$5$美分硬币数量，并确定实际可用的最大值。计算至少需要的$5$美分硬币数量，确保剩余金额能被$1$美分硬币完全覆盖。

1美分硬币：

计算剩余的$1$美分硬币数量 $d$。如果 $d$ 小于$0$或大于可用的$1$美分硬币数量，跳过当前循环。最后输出结果。

C++实现：

#include <bits/stdc++.h>
using namespace std;
int main(){
    double A;
    int B,C,D,E;
    while(scanf("%lf %d %d %d %d",&A,&B,&C,&D,&E)==5){
        int total=(int)round(A*100.0);
        int min=INT_MAX;
        int ga=-1,gb=-1,gc=-1,gd=-1;
        int tempa=total/25;
        int amax;
        if(B<tempa){
            amax=B;
        }else{
            amax=tempa;
        }
        for(int a=0; a<=amax; a++){
            int aftera=total-25*a;
            if(aftera<0){
			continue;
		}
            int tempb=aftera/10;
            int bmax;
            if(C<tempb){
                bmax=C;
            }else{
                bmax=tempb;
            }
            for(int b=0; b<=bmax; b++){
                int afterb=aftera-10*b;
                if(afterb<0){
				continue;
			}
                int tempc=afterb/5;
                int cmax;
                if(D<tempc){
                    cmax=D;
                }else{
                    cmax=tempc;
                }
                int minc=(afterb-E+4)/5;
                if(minc<0){
                    minc=0;
                }
                if(minc>cmax){
                    continue;
                }
                if(cmax<minc){
                    cmax=minc;
                }
                int c=cmax;
                int d=afterb-5*c;
                if(d<0|| d>E){
				continue;
			}

                int total=a+b+c+d;
                if(total<min){
                    min=total;
                    ga=a;
                    gb=b;
                    gc=c;
                    gd=d;
                }
            }
        }
        if(ga==-1){
            printf("NO EXACT CHANGE\n");
        }else{
            printf("%d %d %d %d\n",ga,gb,gc,gd);
        }
    }
    return 0;
}