| Exact Change Only |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Problem 10838 : No special judgement |
| Problem description |
| Boudreaux reached over and shook awake Thibodeaux, who had dozed off somewhere in New Mexico. "Where we at?" Thibodeaux groggily yawned.
"Not in Vegas, I gua-ran-tee, but could you get my knapsack?" Boudreaux asked, gesturing to the worn, leather backpack in the back seat of their cherry red Ford Miata. "Why, is there a problem?" "Just hand me my knapsack, problem or not." Thibodeaux complied, glancing up as Boudreaux slowed the car to a stop in a line of vehicles approaching a toll booth. "$1.65 -- Exact change only," Thibodeaux read the yellow sign on the front of a small wooden building occupied by a lone toll booth operator. "I have to get $1.65 in exact change?" Thibodeaux asked, digging through the knapsack, "all I have are ten quarters, four dimes, and three pennies. I don't have any nickels . . ." "Just give me five of the quarters and the four dimes," Boudreaux replied, holding out his hand. "Oh yeah," Thibodeaux said, handing over the coins, "that does add up to $1.65. I wish there were an easy way to figure out if you have an exact monetary amount, given a set of coins." "Hmmm," Boudreaux shrugged, "sounds like a good programming problem." |
| Input |
| Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 1 component:
|
| Output |
For each data set, there will be exactly one line of output. If there exists one or more subsets of the given coins whose values add up to the given monetary amount exactly, the output will be a single line in the form: A B C Dwhere A is the number of quarters, B is the number of dimes, C is the number of nickels, and D is the number of pennies, for the subset with the fewest number of coins. Otherwise, the output will be a single line with the statement: NO EXACT CHANGE |
| Sample Input |
0.45 2 1 1 4 0.75 3 7 1 75 |
| Sample Output |
NO EXACT CHANGE 3 0 0 0 |
| Problem Source |
| 2003 South Central USA Regional Programming Contest |
输入： A B C D E
A 表示待转换的钱，一个B价值0.25, C,D,E 分别为 0.1,0.05,0.01
要求用最少的B， C， D ，E 个数 表示出 A， 一般的贪心算法会出错，如数据：
1.65 10 4 0 3 ， 仔细观察发现，如果贪心有解则必定是最优的，如果用贪心无解则很可能是贪心出错了。
/// 下面是我的代码，其实也是贪心，解决了贪心无解时的问题
#include <iostream>
using namespace std;
int main(){
double n;
int a,b,c,d,as,bs,cs,ds,m,save;
for(; cin>>n>>as>>bs>>cs>>ds;){
save = m = (int)(n*100+0.01);
for(d=0; d<=ds; d++)
for(c=0; c<=cs; c++)
for(b=0; b<=bs; b++)
for(a=0; a<=as; a++)
if(a*25+b*10+c*5+d==save)
goto over;
over: if(d > ds)
cout<<"NO EXACT CHANGE"<<endl;
else
cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
}
return 0;
}
代码WA了一大片，最后是因为 开始的浮点数转整数出了问题, 这个知识点是，当输入
1.0 时 n 有可能是 0.999999 ，总之输入个浮点数，一般情况下都不是确切输入的那个浮点数。。。。
评论