一：題目

設(shè)有6 種不同面值的硬幣，各硬幣的面值分別為5 分，1 角，2 角，5 角，1 元，2元。現(xiàn)要用這些面值的硬幣來購物。在購物中希望使用最少個數(shù)硬幣。例如，1 次購物需要付款0.55 元，如果沒有5 角的硬幣，只好用22角+11角+1*5分 共4 枚硬幣來付款。

對于給定的各種面值的硬幣個數(shù)和付款金額，計算使用硬幣個數(shù)最少的交易方案。

輸入格式:
輸入數(shù)據(jù)有若干組，第一行給出一個整數(shù)n表示輸入數(shù)據(jù)的組數(shù)。

以下n行每一行有6 個整數(shù)和1個有2 位小數(shù)的實數(shù)。分別表示可以使用的各種面值的硬幣個數(shù)和付款金額。

輸出格式:
輸出每組數(shù)據(jù)的最少硬幣個數(shù)。如果不可能完成交易，則輸出“impossible”。

輸入樣例:

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

輸出樣例:

4 4

二：思路

思路：
1.map容器進行存儲 鍵值為面值（0.05，0.1，0.2，0.5，1，2） 關(guān)鍵值為對應(yīng)的硬幣個數(shù)
2.將付款金額跟面值進行比較，找到剛好大于其面值的銀幣，并判斷其個數(shù)是否有無,
1>:如果其個數(shù)為0就繼續(xù)往下尋找銀幣，直到銀幣個數(shù)不為0為止
2>:如果其個數(shù)不為0的話那么我們就選擇 小于 付款金額的 銀幣數(shù) 并記錄個數(shù)
付款金額 = 付款金額 - 面值*銀幣數(shù);

當(dāng)付款金額小于面值的時候繼續(xù)往下尋找更小的面值
當(dāng)銀幣數(shù)不夠了也是往下繼續(xù)尋找最小隱蔽數(shù)

3.如果最后的付款金額不為0,那么就是 impossible

測試數(shù)據(jù):2
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55

4.注意處理數(shù)據(jù)中的小數(shù)問題，因為double 存的數(shù)據(jù)和真實的并不一樣
eg :比如存入的是0.95 其實是0.9499999999182，那么當(dāng)數(shù)據(jù)剩下0.0499909
那么它和0.05就無法比較了

三：關(guān)于處理double類型數(shù)據(jù)的精度問題

1.問題展示

問題描述：我們明明輸入的是double類型的 0.95 但通過調(diào)試我們發(fā)現(xiàn)其實他是 0.949999999，

2.回歸本題

本題但這中的測試用例1中有0.95這個付款金額，那么我們選擇銀幣的時候，會選擇一個 0.5，兩個0.2，那么還剩0.05,
剩下0.05是我們希望的正常情況，但是通過上方的演示，我們發(fā)現(xiàn)其是真實的值是小于0.05的，那么這樣的話就會影響我們計算銀幣的個數(shù)，因為統(tǒng)計不到0.05的銀幣個數(shù)

3.解決問題

本題當(dāng)中自我感覺很開竅的地方，我們給付款金額加上0.00001，這樣就能保證我的數(shù)據(jù)最起碼是大于面值的，最后的余額再跟0.00001比較，如果小于其就是可以完全換成金幣個數(shù)的。注意這里不能是等于0.00001，因為確實是兩個數(shù)不相等，而且即便你將調(diào)試顯示的數(shù)抄上去都不行！！！

四：上碼

/**思路：1.map容器進行存儲 鍵值為面值（0.05，0.1，0.2，0.5，1，2） 關(guān)鍵值為對應(yīng)的硬幣個數(shù)2.將付款金額跟面值進行比較，找到剛好大于其面值的銀幣，并判斷其個數(shù)是否有無,1>:如果其個數(shù)為0就繼續(xù)往下尋找銀幣，直到銀幣個數(shù)不為0為止2>:如果其個數(shù)不為0的話那么我們就選擇 小于 付款金額的 銀幣數(shù) 并記錄個數(shù) 付款金額 = 付款金額 - 面值*銀幣數(shù);當(dāng)付款金額小于面值的時候繼續(xù)往下尋找更小的面值當(dāng)銀幣數(shù)不夠了也是往下繼續(xù)尋找最小隱蔽數(shù)3.如果最后的付款金額不為0,那么就是 impossible 測試數(shù)據(jù):22 4 2 2 1 0 0.952 4 2 0 1 0 0.55 4.注意處理數(shù)據(jù)中的小數(shù)問題，因為double 存的數(shù)據(jù)和真實的并不一樣eg :比如存入的是0.95 其實是0.9499999999182，那么當(dāng)數(shù)據(jù)剩下0.0499909那么它和0.05就無法比較了 */#include<bits/stdc++.h>using namespace std;int res(vector<double>& v){map<double,double>m;map<double,double>:: reverse_iterator t;int length = v.size();float pay = 0.00001; //付款金額 int cnt = 0;//統(tǒng)計銀幣個數(shù) for(int i = length - 1; i >= 0; i--){if(i == 0) m[0.05] = v[i];if(i == 1) m[0.1] = v[i];if(i == 2) m[0.2] = v[i];if(i == 3) m[0.5] = v[i];if(i == 4) m[1] = v[i];if(i == 5) m[2] = v[i]; if(i == 6) pay += v[i];}for(t = m.rbegin(); t != m.rend(); t++){if(pay >= t->first && t->second != 0){//如果付款金額大于其面值 并且該面值銀幣數(shù)不為0 for(int i = 0; i < t->second; i++){if(pay >= t->first){//這里確保每次的付款金額均大于面值 pay = pay - t->first;cnt++; }else{break;}}} }//cout << cnt;// cout << pay << endl;//0.00999999139 if(pay <= 0.001){return cnt;// cout << "wyj";}return -1; }int main(){int n;cin >> n;for(int i = 0; i < n; i++){vector<double>v;for(int i = 0; i < 7; i++){double nums;cin >> nums;v.push_back(nums);}int ans = res(v);if(ans == -1){cout << "impossible" << endl;}else{cout << ans << endl;}} } //2//2 4 2 2 1 0 0.95//2 4 2 0 1 0 0.55//////1//2 4 2 2 1 0 0.95//1//2 4 2 2 1 0 0.05////1//2 4 2 2 1 0 0.95

五：知識速遞（如果對map容器不熟悉的兄弟們可以了解下）

map的逆序遍歷
map的基本用法

又得嘮叨一句 記得加油 寶！！！！！！！！！！！！！！！!！!！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的7-7 硬币找钱问题 (10 分)（思路+详解+double类型数据的处理）Come baby!!!!!!!!!!!!!!!!!!!!的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。