硬币找钱问题
问题描述
设有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
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];//各面值硬币数
10 int count=0;//需要的最少硬币数
11 int cost,c[6]={ 5, 10,20,50,100,200};//需支付数和硬币面值,以分计算
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);//将输入的钱转为 分
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 //检查一个数的后面是否还有硬币，如果没有了,或者余下的硬币的和小于要找的值。那么就只能用当前硬币来计算了
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 //检查是否可以用当前的币值来支付
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
崔佳星 阅读(2218)
评论(6) 编辑 收藏 引用