复制的题解 ① 这是一个典型的贪心问题，每一次都要在找到比当前该凑数钱小的最大面值数，这样就可以在钱币数量相同的情况下可拼凑价值最大

贪心问题需要自己慢慢悟，不说多了，放代码

//shopping
#include<iostream>  
#include<cstdio>  
#include<algorithm>  
using namespace std; 
const int Maxn=1005;  
int n,x,s[Maxn],ans; 
int main()
{  
    int i,j,sum;
    cin>>x>>n;  
    for(i=1;i<=n;i++)cin>>s[i]; 
    sort(s+1,s+1+n); //面值从小到大排序
    if(s[1]!=1)//肯定无解
    {cout<<-1<<endl;   return 0;}  
    sum=0;//sum已经可以凑的钱
    while(sum<x)
    {  
        for(i=n;i>=1;i--)   
            if(s[i]<=sum+1)break;//凑下一个,找可用最大面值的
        ans++;    //选面值s[i]的硬币
        sum+=s[i];//已经凑好的sum,中间间隔s[i]个凑法做过了
    }   
    printf("%d\n",ans);
    return 0;
}

② 假设 ， 我们现在已经可以组合出0-m块钱的任意数值，如果我们加上一个小于等于m+1数值的硬币a[i]，那么对于之前可以凑出的任意数值我们都可以加上这枚硬币a[i],那么我们可以凑出的数值就变成了0-m+a[i]。

至于为什么是小于等于m+1，如果我们的新取硬币是大于m+1的，那么哪怕是加上最小的0，值也是大于m+1，所以我们能够凑出的连续区间仍然是1-m。

综上，因为加上一枚小于等于m+1的新硬币，那么在满足小于等于m+1这个条件的同时越大越好（因为区间会变成0-m+a[i]）。

正确性是显而易见的，因为我们做出的任意一个决策都是只会影响下一个的m，让m尽可能的大，m大会间接影响a[i]变大，而我们也希望让a[i]尽可能大，那么可以证明这个策略是正确。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[15];
int main() {
	int x , n;
	scanf("%d %d" , &x , &n);
	for (int i = 1; i <= n; ++i) scanf("%d" , &a[i]);
	sort(a + 1 , a + 1 + n);//排序，方便我们选择最优决策
	int tot = 0 , ans = 0;//tot记录上述分析的m值，初始时我们只能凑出0-0的值，ans记录答案
	while(1) {
		if(tot >= x) {//如果我们能凑出的区间大于了目标区间，就返回
			printf("%d" , ans);
			return 0;
		}
		else ans ++;//否则继续贪心
		int f = 1;
		for (int i = n; i >= 1; --i) {//从大到小查询
			if(a[i] <= tot + 1) { // 如果满足条件，那么一定是最优的（因为从小到大找）
				tot += a[i];//更新区间
				f = 0;
				break;
			}
		}
		if(f) {//如果无法满足条件则不可能使tot值再增加
			printf("-1");
			return 0;
		}
	}
	return 0;
}