資源簡介
硬幣找錢問題
問題描述
設有6種不同面值的硬幣,各硬幣的面值分別為5分,1角,2角,5角,1元,2元。現要用這些面值的硬幣來購物和找錢。購物時規定了可以使用的各種面值的硬幣個數。
假定商店里各面值的硬幣有足夠多,顧客也可用多種方式支付。在1次購物中希望使用最少硬幣個數。例如,1次購物需要付款0.55元,沒有5角的硬幣,只好用2*20+10+5共4枚硬幣來付款。如果付出1元,找回4角5分,同樣需要4枚硬幣。但是如果付出1.05元(1枚1元和1枚5分),找回5角,只需要3枚硬幣。這個方案用的硬幣個數最少。
您的任務:對于給定的各種面值的硬幣個數和付款金額,計算使用硬幣個數最少的交易方案。
輸入
有若干行測試數據。每一行有6個整數a5、a4、a3、a2、a1、a0和1個有2位小數的實數money,分別表示5分,1角,2角,5角,1元,2元面值的硬幣個數和付款金額,money<=1000。文件以6個0結束(不必處理)。
輸出
對每一行測試數據,一行輸出最少硬幣個數。如果不可能完成交易,則輸出“impossible”。
輸入樣例
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
0 0 0 0 0 0
輸出樣例
2
3

代碼片段和文件信息
#include?
#include?
using?namespace?std;
int?coins[6];//各面值硬幣數
int?count=0;//需要的最少硬幣數
int?costc[6]={?5?102050100200};//需支付數和硬幣面值以分計算
ifstream?input(“input.txt“)?;
ofstream?output(“output.txt“);
void?getData()
{
for(int?i=0;i<6;i++)
{
input>>coins[i];
}
double?costt;
input>>costt;
cost=(int)(costt*100);//將輸入的錢轉為?分
cout< for(?i=0;i<6;i++)
{
cout< }
}
int?contains(int?a)
{
for(int?i=0;i<6;i++)
{
if(c[i]==a&&coins[i]>0)return?i;
}
return?-1;
}
void?getMinCount()
{
for(int?i=5;i>=0;i--)
{
if(coins[i]>0)
{ int?*cc=(int?*)malloc((i+1)*sizeof(int));//開辟新數組來保存虛擬幣值的數量
???? cc[0]=0;
for(int?k=1;k {
cc[k]=c[k-1];
}
for(int?j=0;j<1+i;j++)
{
if(cost>=(c[i]-cc[j]))
{
if(coins[i]>=cost/(c[i]-cc[j]))//當前面值硬幣如果足夠支付余額
{ count+=cost/(c[i]-cc[j])+1;
if(contains(c[i]-cc[j])!=-1)
{
count--;//如果消費者具有該硬幣,則無需使用找零,因為找零需要耗費2個硬幣,而支付只需要一個硬幣
coins[contains(c[i]-cc[j])]-=cost/(c[i]-cc[j]);//相應硬幣數減少
}
else?coins[i]-=cost/(c[i]-cc[j]);//找零法相應硬幣數減少
// cout< cost=cost%(c[i]-cc[j]);
if(contains(c[i])==-1)break;//如果該硬幣用完,無需繼續計算,用下一個小面值的吧
}
else?//如果當前幣值不夠支付,則用完該幣值
{
count+=coins[i];
cost=cost-c[i]*coins[i];
coins[i]=0;
}
?
}
}
}
}
if(count==0||cost!=0){cout< else
{
cout< for(?i=0;i<6;i++)
{
cout< }
cout< }
}
void?main()
{
while(!input.eof())
{
count=0;
getData();
???? getMinCount();
}
input.close();
output.close();
}
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件?????????82??2011-04-07?10:15??input.txt
?????文件???????2136??2011-04-07?10:42??4-3.cpp
-----------?---------??----------?-----??----
?????????????????2218????????????????????2
- 上一篇:編寫推箱子游戲程序第三步——選擇游戲關卡
- 下一篇:重慶行政區劃
評論
共有 條評論