题目描述

你就要去购物了，现在你手上有N种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出1到X之间的任意值。

题目分析

题目要求组合出1到X之间的任意值，那么面值之中没有1的话就无法组合出1，所以面值中没有1即为无解的情况，而1也是必须要选的面值。

对于值T，若我们已经能够组合出1~T-1中所有的值，而T是当前选用的硬币无法组合出的，那么我们再选一个面值为V(V≤T)的硬币，则T=T-V+V，其中T-V是我们已经能够组合出的值。同时，我们使用这些硬币还可以组合出V+1~V+T-1中所有的值，下一个无法组合的值就可以从V+T开始考虑。由于我们要求硬币的最小值，我们每次选择硬币中满足条件的最大面值即可。

代码

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int t[11]={
    0,1,2,5,10,20,50,100,200,500,1000}; 5 int x,n,ans,a[11]; 6 bool vis[1001]; 7 int main() 8 { 9     scanf("%d%d",&x,&n);10     for(int i=1;i<=n;++i)11         scanf("%d",&a[i]);12     sort(a+1,a+n+1);13     if(a[1]!=1)14         puts("-1");15     else16     {17         for(int now=1;now<=x;)18             for(int i=n;i>0;--i)19                 if(a[i]<=now)20                 {21                     now+=a[i];22                     ++ans;23                     break;24                 }25         printf("%d",ans);26     }27     return 0;28 }