你就要去购物了，现在你手上有 N 种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出 1 到 X 之间的任意值。
输出最少需要携带的硬币个数，如果无解输出 -1。
思路：
- 显然，当且仅当面值没有 1 时，ans 无解。
- 若存在面值为 1 的硬币，那么我们从小到大依次判断是否能组合出 1 到 X 之间的任意面值。
- 设 sum 为当前可以凑出的最大面值，ans 为目前携带的硬币个数。（初始时，sum = 0，ans = 0）
- 可以先找到小于等于 sum + 1 的最大面值为 a[i] 的硬币，那么则可以凑出 1 到 sum + a[i] 之间的任意面值，即每找到一个小于等于 sum + 1 的最大面值的硬币，则 ans++，并更新 sum 为 sum + a[i]，直到 sum ≥ X。
证明：
- 首先，先证明为什么找到了小于等于 sum + 1 的最大面值为 a[i] 的硬币，就可以凑出 1 到 sum + a[i] 之间的任意面值。
- 由于 sum 为当前可以凑出的最大面值，所以可以保证目前可以凑出 1 到 sum 之间的任意面值。此时，问题转化为是否可以凑出 sum + 1 到 sum + a[i] 之间的任意面值。
- 由于加入了面值为 a[i] 的硬币，所以只需要再凑出 (sum + 1) - a[i] 到 (sum + a[i]) - a[i] 之间的任意面值即可。因为 a[i] ≤ sum + 1，所以保证了 (sum + 1) - a[i] ≥ 0。
- 同时，(sum + 1) - a[i] 到 （sum + a[i]) - a[i] 小于等于 sum，这意味着可以组合出该区间内的任意面值，命题得证。
- 然后，再证明每次要找小于等于 sum + 1 的最大面值的硬币为最优解，即该方案可以保证携带的硬币个数最少。
- 设 Ans 为正确答案（最少需要携带的硬币个数），cnt 为按照思路求解的结果，显然 Ans ≤ cnt。
- 此时，只需证明 Ans ≥ cnt 即可。如果选取大于 sum + 1 的面值的硬币，则不能凑出 sum + 1 的面值，还需再添一枚硬币才行，此时所需的硬币个数不可能减少。如果选取的是小于等于 sum + 1 的面值的硬币，但不是最大面值，那么一定可以用最大面值来进行替换，所以 cnt 一定是最优解，即 Ans ≥ cnt。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int x, n;
int a[20];
int sum;
int ans;
int main()
{
cin >> x >> n;
bool f = false;
for(int i = 0; i < n; i++)
{
cin >> a[i];
if(a[i] == 1) f = true;
}
if(!f)
{
cout << "-1" << endl;
return 0;
}
sort(a, a + n);
while(sum < x)
{
int i;
for(i = n - 1; i >= 0; i--)
{
if(a[i] <= sum + 1) break;
}
ans++;
sum += a[i];
}
cout << ans << endl;
return 0;
}