钱币问题

钱币问题"/>

钱币问题

用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100， 用来凑 15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等

你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。

#include <iostream>
#include <algorithm>//是c++特有的STL模板的算法头文件包括sort(),stable_sort()等等
using namespace std;
int main()
{
 int money,n,i,s,a[10];
 printf("输入要凑钱的总数为：");
 while(cin>>money)
 {
  s=0;
  if(money==0) break;
  cin>>n;
  printf("给定的%d种钱币面值为：",n);
  for(i=0;i<n;i++)
  {
   cin>>a[i];
  }
  sort(a,a+n);//排序
  for(i=n-1;i>=0;i--)
  {
   if(money>=a[i])
   {
    s=s+money/a[i];
    money=money%a[i];
   }
   if(money==0) break;
  }
  if(money!=0) 
cout<<"Impossible"<<endl;
  else 
     printf("最少需要%d个钱币才能凑成某个给出的钱数",s);
 }
 return 0;
}