贪心算法（又称贪婪算法，greedy algorithm）是指， 总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，而是局部 最优解 。 无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
http://acm.hdu.edu.cn/showproblem.php?pid=3348
Problem Description "Yakexi, this is the best age!" Dong MW works hard and get high pay, he has many 1 Jiao and 5 Jiao banknotes(纸币), some day he went to a bank and changes part of his money into 1 Yuan, 5 Yuan, 10 Yuan.(1 Yuan = 10 Jiao) "Thanks to the best age, I can buy many things!" Now Dong MW has a book to buy, it costs P Jiao. He wonders how many banknotes at least,and how many banknotes at most he can use to buy this nice book. Dong MW is a bit strange, he doesn't like to get the change, that is, he will give the bookseller exactly P Jiao. Input T(T<=100) in the first line, indicating the case number. T lines with 6 integers each: P a1 a5 a10 a50 a100 ai means number of i-Jiao banknotes. All integers are smaller than 1000000. Output Two integers A,B for each case, A is the fewest number of banknotes to buy the book exactly, and B is the largest number to buy exactly.If Dong MW can't buy the book with no change, output "-1 -1". Sample Input 3 33 6 6 6 6 6 10 10 10 10 10 10 11 0 1 20 20 20 Sample Output 6 9 1 10 -1 -1
/*
求最少的时候，从大到小检索，尽可能用更多的大面额。这里还是比较简单的。
求最多的时候有些困难，转化一下！ 如果说 用的钞票最多的话，那么就是手里剩余钞票最少！！
*/
#include<iostream> #include<cstdio> #include<cmath> #include<stdio.h> #include<algorithm> using namespace std; int mianzhi[6]= {0,1,5,10,50,100}; int main() { int t; cin>>t; while(t--) { int mon,m,a[6],b[6],min=0,max=0,sum=0,z=0; cin>>mon; m=mon; for(int i=1; i<6; i++) { cin>>a[i]; b[i]=a[i]; z+=a[i]; } for(int i=1; i<6; i++) sum+=a[i]*mianzhi[i]; for(int i=5; i>0; i--)//min { while(m>=mianzhi[i]&&b[i]>0) { m-=mianzhi[i]; b[i]--; min++; } } if(m) { cout<<"-1 -1"<<endl; continue; } m=mon,max=0; for(int i=1; i<6; i++) b[i]=a[i]; int k=sum-m; for(int i=5; i>0; i--)//max { while(k>=mianzhi[i]&&b[i]>0) { k-=mianzhi[i]; b[i]--; max++; } } cout<<min<<" "<<z-max<<endl; } return 0; }
