包子凑数【蓝桥杯】/完全背包

包子凑数

完全背包

完全背包问题和01背包的区别就是，完全背包问题每一个物品能取无限次。
思路：当n个数的最大公约数不为1，即不互质时，有无限多个凑不出来的，即n个数都可以表示成kn，k为常数且不为1。当n个数的最大公约数为1，到了某个数之后就全都可以凑出来。
根据本题的数据，可以直接遍历到10010就行

#include<iostream>
using namespace std;
//dp[i]表示i这个数可不可以被凑出来
int dp[10010];
//欧几里得算法求最大公约数
int gcd(int a,int b)
{return (b==0)?a:gcd(b,a%b);
}
int main()
{int n;cin>>n;int a[n],g;for(int i=0;i<n;i++) {cin>>a[i];if(i==0) g=a[i];else g=gcd(g,a[i]);}if(g!=1){cout<<"INF"<<endl;return 0;}dp[0]=1;//完全背包for(int i=0;i<n;i++){for(int j=a[i];j<10010;j++){dp[j]=max(dp[j],dp[j-a[i]]);}}int ans=0;for(int i=0;i<10010;i++){if(!dp[i]) ans++;}cout<<ans<<endl;return 0;
}