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

int Coins[6];?? ??? ??? ??? ??? ??? ??? ??? ??? ? ? // 各面值硬幣數(shù)
int CoinNum = 0;?? ??? ??? ??? ??? ??? ??? ??? ? ? // 需要的最少硬幣數(shù)
int Pay;?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ? ? // 需要支付的錢數(shù)
int CoinValue[6] = {5, 10, 20, 50, 100, 200};?? ? ? // 硬幣面值，以分為單位
int ChangeValue[7] = {0, 5, 10, 20, 50, 100, 200}; // 用來找零的硬幣面值，0為不找零的情況
int RealMoney = CoinValue[0] - ChangeValue[0];?? ? ? // 實際支付金額 = 支付硬幣 - 找零硬幣 【貪心變量】
ifstream input("input.txt");
ofstream output("output.txt");

/*****************************************************************
* 函數(shù)描述： 從文件中讀取測試數(shù)據(jù)
*****************************************************************/
void getData()
{
?? ?for (int i = 0; i < 6; ++i)
?? ??? ?input >> Coins[i];
?? ?double costt;
?? ?input >> costt;
?? ?cout << "\n目標金額：" << costt << "元"
?? ??? ? << "\n各幣值數(shù)量：" << endl;
?? ?Pay = (int)(costt * 100); //將輸入的錢轉(zhuǎn)為分為單位
?? ?for (int i = 0; i < 6; ++i)
?? ??? ?cout << Coins[i] << " ";
}

/*****************************************************************
* 函數(shù)描述： 格式化輸出結(jié)果
*****************************************************************/
void outputResult()
{
?? ?if (CoinNum == 0 || Pay != 0)
?? ?{
?? ??? ?cout << "\n============== impossible" << endl;
?? ??? ?output << "impossible" << endl;
?? ?}
?? ?else
?? ?{
?? ??? ?cout << endl
?? ??? ??? ? << "各幣值剩余數(shù)量:" << endl;
?? ??? ?for (int i = 0; i < 6; i++)
?? ??? ??? ?cout << Coins[i] << " ";
?? ??? ?cout << endl
?? ??? ??? ? << "============== 支付和找零需要的最少總硬幣數(shù)量：" << CoinNum << endl;
?? ??? ?output << CoinNum << endl;
?? ?}
}

/*****************************************************************
* 函數(shù)描述：查看顧客手中是否還有 a 面值的硬幣，
* ? ? ? ? ?如果有則返回面值索引，否則返回 -1
* 函數(shù)返回：面值索引 or -1
*****************************************************************/
int contains(int a)
{
?? ?for (int i = 0; i < 6; ++i)
?? ??? ?if (CoinValue[i] == a && Coins[i] > 0)
?? ??? ??? ?return i;
?? ?return -1;
}

/*****************************************************************
* 函數(shù)描述： 貪心法實現(xiàn)硬幣找零問題，以實際支付金額作為貪心變量
*****************************************************************/
void Greed()
{
?? ?// 顧客手中的硬幣面值從大到小遍歷選取
?? ?for (int i = 5; i >= 0; --i)
?? ?{
?? ??? ?if (Coins[i] > 0) // 如果顧客手中當前面值硬幣有剩余
?? ??? ?{
?? ??? ??? ?// 商家手中的硬幣從小到大遍歷選取，進行找零操作
?? ??? ??? ?for (int j = 0; j <= i; ++j)
?? ??? ??? ?{
?? ??? ??? ??? ?RealMoney = CoinValue[i] - ChangeValue[j]; // 實際支付金額 = 支付硬幣 - 找零硬幣
?? ??? ??? ??? ?// 只有當實際支付金額小于目標金額的時候才進行選取，否則需要增加找零硬幣的金額（即，繼續(xù)本層循環(huán) j）
?? ??? ??? ??? ?if (Pay >= RealMoney)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if (Coins[i] >= Pay / RealMoney) //如果當前面值硬幣找零后足夠支付余額
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?int TempCoinNum = Pay / RealMoney; // 此步驟顧客消耗硬幣數(shù)量
?? ??? ??? ??? ??? ??? ?CoinNum += TempCoinNum * 2;
?? ??? ??? ??? ??? ??? ?// 如果顧客具有該硬幣，則無需使用找零，因為找零需要耗費2個硬幣，而支付只需要一個硬幣
?? ??? ??? ??? ??? ??? ?if (contains(RealMoney) != -1)
?? ??? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ??? ?TempCoinNum = min(TempCoinNum, Coins[contains(RealMoney)]);
?? ??? ??? ??? ??? ??? ??? ?CoinNum -= TempCoinNum;
?? ??? ??? ??? ??? ??? ??? ?Coins[contains(RealMoney)] -= TempCoinNum; // 顧客手中相應(yīng)硬幣數(shù)減少
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ??? ?else
?? ??? ??? ??? ??? ??? ??? ?Coins[i] -= Pay / RealMoney; // 顧客手中當前面值硬幣數(shù)減少
?? ??? ??? ??? ??? ??? ?Pay = Pay % RealMoney;?? ??? ??? ? // 更新還需支付的金額
?? ??? ??? ??? ??? ??? ?if (contains(CoinValue[i]) == -1)
?? ??? ??? ??? ??? ??? ??? ?break; // 如果顧客手中該硬幣用完，直接用下一個小面值
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?else // 如果當前幣值不夠支付，則用完該幣值
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?CoinNum += Coins[i];
?? ??? ??? ??? ??? ??? ?Pay = Pay - CoinValue[i] * Coins[i];
?? ??? ??? ??? ??? ??? ?Coins[i] = 0;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ?}
}

int main()
{
?? ?while (!input.eof())
?? ?{
?? ??? ?CoinNum = 0;
?? ??? ?getData();?? ??? ?// 讀取測試數(shù)據(jù)
?? ??? ?Greed();?? ??? ?// 貪心法實現(xiàn)硬幣找零問題
?? ??? ?outputResult(); // 輸出結(jié)果
?? ?}
?? ?input.close();
?? ?output.close();
}

?

總結(jié)

以上是生活随笔為你收集整理的找钱问问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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