你就要去购物了，现在你手上有N种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出1到X之间的任意值。
输入格式：
第一行两个数X、N，以下N个数，表示每种硬币的面值。
【数据规模】
对于30%的数据，满足N≤3，X≤20;
对于100%的数据，满足N≤10，X≤1000.
输出格式：
最少需要携带的硬币个数，如果无解输出-1.
20 4 1 2 5 10
5
将面值从小到大排序
考虑用前ii种面值可以凑出的最大价值
显然当且仅当a_1\neq 1a1?≠1时是无解的，因为凑不出11
这样就限定了a_1=1a1?=1
假设已经凑出了11~ss的面值，那么我们可以加入一张面值不超过s+1s+1的硬币
如果超过s+1s+1，那么就不可以凑出s+1s+1面值
设这个面值是aa，那么可以把ss延伸到s+as+a
显然这个面值越大越好
所以就直接找出a\leq s+1a≤s+1的最大的aa,然后把ss更新为s+as+a,同时ans++ans++即可
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int n,x,a[2000],ans; int getin() { int x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-48,ch=getchar(); return x; } int main() { x=getin(),n=getin(); for(int i=1;i<=n;i++)a[i]=getin(); sort(a+1,a+n+1); if(a[1]!=1){cout<<-1;return 0;} int sum=0; while(sum<x) { int i; for(i=n;i>=1;i--)if(a[i]<=sum+1)break; ans++,sum+=a[i]; } cout<<ans<<endl; }
原文：https://www.cnblogs.com/bxd123/p/10993225.html
