硬币找钱问题 (10 分)
设有6 种不同面值的硬币,各硬币的面值分别为5 分,1 角,2 角,5 角,1 元,2元。
现要用这些面值的硬币来购物。在购物中希望使用最少个数硬币。
例如,1 次购物需要付款0.55 元,如果没有5 角的硬币,只好用2*2角+1*1角+1*5分 共4 枚硬币来付款。
对于给定的各种面值的硬币个数和付款金额,计算使用硬币个数最少的交易方案。
输入格式:
输入数据有若干组,第一行给出一个整数n表示输入数据的组数。
以下n行每一行有6 个整数和1个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。
输出格式:
输出每组数据的最少硬币个数。如果不可能完成交易,则输出“impossible”
//针对于单组数据进行的处理方法函数
int solution(float a[]) {
float money = a[6];//记录支付金额
int num = 0;//使用硬币个数
//当金额大于等于2元并且2元硬币个数大于0,优先使用2元硬币
while (money >= 2 && a[5] > 0) {
money -= 2;
num++;
a[5]--;
}
//当金额大于等于1元并且1元硬币个数大于0,优先使用1元硬币
while (money >= 1 && a[4] > 0) {
money -= 1;
num++;
a[4]--;
}
//当金额大于等于0.5元并且0.5元硬币个数大于0,优先使用0.5元硬币
while (money >= 0.5 && a[3] > 0) {
money -= 0.5;
num++;
a[3]--;
}
//当金额大于等于0.2元并且0.2元硬币个数大于0,优先使用0.2元硬币
while (money >= 0.2 && a[2] > 0) {
money -= 0.2;
num++;
a[2]--;
}
//当金额大于等于0.1元并且0.1元硬币个数大于0,优先使用0.1元硬币
while (money >= 0.1 && a[1] > 0) {
money -= 0.1;
num++;
a[1]--;
}
//当金额大于等于0.05元并且0.05元硬币个数大于0,优先使用0.05元硬币
while (money >= 0.05 && a[0] > 0) {
money -= 0.05;
num++;
a[0]--;
}
//如果经过以上处理,money的数值仍不为0,则说明支付失败
if (money != 0) {
num = -1;
}
//返回使用的硬币数目
return num;
}
int main() {
int n, flag;
cin >> n;
//定义n行7列的二维数组存储数据
float a[n][7];
for (int i = 0; i < n; ++i) {
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3] >> a[i][4] >> a[i][5] >> a[i][6];
}
//分别对每一行数据进行处理
for (int j = 0; j < n; ++j) {
flag = solution(a[j]);
//如果flag大于等于0说明支付成功,若小于0说明支付失败
if (flag >= 0)cout << flag;
else cout << "impossible";
if (j != n - 1)cout << "\n";
}
}