Problem 1369 --算法实现题 4-11 硬币找钱问题（习题 4-24）

1369: 算法实现题 4-11 硬币找钱问题（习题 4-24）

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $19$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心

Description

设有 6 种不同面值的硬币，各硬币的面值分别为 5 分，1 角，2 角，5 角，1 元，2 元。

现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组

Coins[1:6]中，商店里各面值的硬币有足够多。在 1 次购物中希望使用最少硬币个数。
例如，1 次购物需要付款 0.55 元，没有 5 角的硬币，只好用 2*20+10+5 共 4 枚硬币来付款。如果付出 1 元，找回 4 角 5 分，同样需要 4 枚硬币。但是如果付出 1.05 元（1 枚 1元和 1 枚 5 分），找回 5 角，只需要 3 枚硬币。这个方案用的硬币个数最少。

算法设计：

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

Input

输入每一行有 6 个整数和 1 个有 2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。文件以 6 个 0 结束。

Output

输出的最少硬币个数。结果应分行输出，每行一个数据。如果不可能完成交易，则输出“impossible”。 

Sample Input复制

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

Sample Output复制

2
3

推荐代码 查看1369 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 董尔垒@网络工程142 84734 2017-04-29 02:11:00

赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛