硬幣找錢問(wèn)題
問(wèn)題描述
設(shè)有6種不同面值的硬幣，各硬幣的面值分別為5分，1角，2角，5角，1元，2元。現(xiàn)要用這些面值的硬幣來(lái)購(gòu)物和找錢。購(gòu)物時(shí)規(guī)定了可以使用的各種面值的硬幣個(gè)數(shù)。
假定商店里各面值的硬幣有足夠多，顧客也可用多種方式支付。在1次購(gòu)物中希望使用最少硬幣個(gè)數(shù)。例如，1次購(gòu)物需要付款0.55元，沒(méi)有5角的硬幣，只好用2*20+10+5共4枚硬幣來(lái)付款。如果付出1元，找回4角5分，同樣需要4枚硬幣。但是如果付出1.05元（1枚1元和1枚5分），找回5角，只需要3枚硬幣。這個(gè)方案用的硬幣個(gè)數(shù)最少。
您的任務(wù)：對(duì)于給定的各種面值的硬幣個(gè)數(shù)和付款金額，計(jì)算使用硬幣個(gè)數(shù)最少的交易方案。
輸入
有若干行測(cè)試數(shù)據(jù)。每一行有6個(gè)整數(shù)a5、a4、a3、a2、a1、a0和1個(gè)有2位小數(shù)的實(shí)數(shù)money，分別表示5分，1角，2角，5角，1元，2元面值的硬幣個(gè)數(shù)和付款金額，money<=1000。文件以6個(gè)0結(jié)束（不必處理）。
輸出
對(duì)每一行測(cè)試數(shù)據(jù)，一行輸出最少硬幣個(gè)數(shù)。如果不可能完成交易，則輸出“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
1 #include <iostream>
2 #include<malloc.h>
3 #include<fstream>
4 using namespace std;
5 ifstream ifs;
6 ofstream ofs;
7
8
9 int coins[6];//各面值硬幣數(shù)
10 int count=0;//需要的最少硬幣數(shù)
11 int cost,c[6]={ 5, 10,20,50,100,200};//需支付數(shù)和硬幣面值,以分計(jì)算
12 bool finish = false;
13 void getData()
14 {
15 int flag = 0;
16 for(int i=0;i<6;i++)
17 {
18 ifs>>coins[i];
19 flag = flag | coins[i];
20
21 }
22 if(!flag)
23 {
24 finish = true;
25 return ;
26 }
27 double costt;
28 ifs>>costt;
29 cost=(int)(costt*100);//將輸入的錢轉(zhuǎn)為 分
30 }
31
32 int contains(int a)
33 {
34 for(int i=0;i<6;i++)
35 {
36 if(c[i]==a&&coins[i]>0)return i;
37 }
38 return -1;
39 }
40
41 int getBackMin(int k)
42 {
43 int count = 0;
44 for(int i = 5;i >=0;--i)
45 {
46 count += k /c[i];
47 k = k % c[i];
48 }
49 return count;
50 }
51
52 //檢查一個(gè)數(shù)的后面是否還有硬幣，如果沒(méi)有了,或者余下的硬幣的和小于要找的值。那么就只能用當(dāng)前硬幣來(lái)計(jì)算了
53 int checkLast(int index,int co)
54 {
55 int sum = 0;
56 for(int i =index - 1;i >=0;--i )
57 {
58 sum += c[i] * coins[i];
59 }
60 if(co <= sum)
61 return 1;
62 else
63 return 0;
64 }
65
66 void getMinCount()
67 {
68 for(int i=5;i>=0;i--)
69 {
70 if(coins[i]>0)
71 { int *cc=(int *)malloc((i+1)*sizeof(int));
72 cc[0]=0;
73 for(int k=1;k<i+1;k++)
74 {
75 cc[k]=c[k-1];
76 }
77 for(int j=0;j<1+i;j++)
78 {
79
80 if(cost>=(c[i]-cc[j]))
81 {
82 if(coins[i]>=cost/(c[i]-cc[j]))
83 { count+=cost/(c[i]-cc[j])+1;
84
85 if(contains(c[i]-cc[j])!=-1)
86 {
87 count--;
88 coins[contains(c[i]-cc[j])]-=cost/(c[i]-cc[j]);
89 }
90 else coins[i]-=cost/(c[i]-cc[j]);
91 cost=cost%(c[i]-cc[j]);
92 if(contains(c[i])==-1)break;
93 }
94 else
95 {
96 count+=coins[i];
97 cost=cost-c[i]*coins[i];
98 coins[i]=0;
99 }
100
101
102 }
103
104 }
105 //剩下的錢不夠支付了
106 if(!checkLast(i,cost))
107 {
108 //檢查是否可以用當(dāng)前的幣值來(lái)支付
109 int hasLest = cost / c[i] + 1;
110 if(hasLest <= coins[i])
111 {
112 count += hasLest;
113 count += getBackMin(c[i] * hasLest - cost);
114 cost = 0;
115 break;
116 }
117 else
118 break; ;
119 }
120 }
121
122 }
123
124 if(count==0||cost!=0){ofs<<"impossible"<<endl;}
125 else
126 {
127 ofs<<count<<endl;
128 }
129
130 }
131
132
133 int main()
134 {
135 ifs.open("input.txt");
136 ofs.open("output.txt");
137 while(!finish)
138 {
139 count=0;
140 getData();
141 if(finish)
142 break;
143 getMinCount();
144 }
145 ifs.close();
146 ofs.close();
147 return 0;
148 }
posted on 2012-04-15 10:33
崔佳星 閱讀(2265)
評(píng)論(6) 編輯 收藏 引用