网站制作 流程,什邡移动网站建设,做网站公众号多少钱,中国施工企业管理协会官网包子凑数 完全背包
完全背包问题和01背包的区别就是#xff0c;完全背包问题每一个物品能取无限次。 思路#xff1a;当n个数的最大公约数不为1#xff0c;即不互质时#xff0c;有无限多个凑不出来的#xff0c;即n个数都可以表示成kn#xff0c;k为常数且不为1。当n个…包子凑数 完全背包
完全背包问题和01背包的区别就是完全背包问题每一个物品能取无限次。 思路当n个数的最大公约数不为1即不互质时有无限多个凑不出来的即n个数都可以表示成knk为常数且不为1。当n个数的最大公约数为1到了某个数之后就全都可以凑出来。 根据本题的数据可以直接遍历到10010就行
#includeiostream
using namespace std;
//dp[i]表示i这个数可不可以被凑出来
int dp[10010];
//欧几里得算法求最大公约数
int gcd(int a,int b)
{return (b0)?a:gcd(b,a%b);
}
int main()
{int n;cinn;int a[n],g;for(int i0;in;i) {cina[i];if(i0) ga[i];else ggcd(g,a[i]);}if(g!1){coutINFendl;return 0;}dp[0]1;//完全背包for(int i0;in;i){for(int ja[i];j10010;j){dp[j]max(dp[j],dp[j-a[i]]);}}int ans0;for(int i0;i10010;i){if(!dp[i]) ans;}coutansendl;return 0;
}
