蓝桥杯算法训练最大体积(gcd+完全背包)

问题描述
　　每个物品有一定的体积（废话），不同的物品组合，装入背包会战用一定的总体积。
假如每个物品有无限件可用，那么有些体积是永远也装不出来的。为了尽量装满背包，
附中的OIER想要研究一下物品不能装出的最大体积。题目保证有解，如果是有限解，
保证不超过2，000，000，000
　　如果是无限解，则输出0
输入格式
　　第一行一个整数n（n<=10），表示物品的件数
　　第2行到N+1行: 每件物品的体积(1<= <=500)
输出格式
　　一个整数ans，表示不能用这些物品得到的最大体积。
样例输入
3
3
6
10
样例输出
17
*/

#include<stdio.h>
#include<string.h>
 int gcd(int a,int b)
 {  if(b==0)return a;
     else return gcd(b,a%b);
 }
 int main()
 {
  int n,t,i,m,a,b;long long int j,ans,t1;int s[20]; long int dp[80003];
  scanf("%d",&n);
  scanf("%d",&s[0]);
    t=s[0];
   for(i=1;i<n;i++)
   { scanf("%d",&s[i]);
     t=gcd(t,s[i]);
     if(s[i]<s[0]){int m=s[0];s[0]=s[i];s[i]=m;}

   }
 if(t==1&&s[0]!=1)
 {    memset(dp,-1,sizeof(dp));t1=0;dp[0]=1;
      for(i=0;i<n;i++)
      for(j=s[i];j<80000;j++)
        {if(dp[j-s[i]]!=-1)dp[j]=1;
         if(i==n-1&&dp[j]==1)
         {t1++;if(t1>=s[0])break;}
          else t1=0,ans=j;
        }
        if(ans==79999)ans=s[0]-1;
         printf("%ld\n",ans);
}
 else printf("0\n");
 return 0;
 }