一个数j如果凑不出来,那么j+w[1],j+w[2],j+w[3],j+w[4]都凑不出来
所以我们判断一个数i是否能凑出来,就看他i减去每一笼数量的情况是否凑的出来,但凡有一个可以,i就可以凑出来(加上那笼即可)
这种代码上和y总的优化后代码是一样的,但思路出发点不一样
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int w[N];
bool f[N*1000];
int ans=0,n;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>w[i];
int t=0;
for(int i=1;i<=n;i++)
t=gcd(w[i],t);
if(t!=1)
{
printf("INF");
return 0;
}
f[0]=true;
for(int i=1;i<=10000;i++)
{
for(int j=1;j<=n;j++)
if(i>=w[j]&&f[i-w[j]])
f[i]=true;
}
for(int i=1;i<=10000;i++)
if(f[i]==false)
ans++;
printf("%d",ans);
}
或者使得每一个能凑出来的j加上w更新为能凑出来的,都行