蓝桥杯算法训练VIP-最大体积 （C语言代码）----------------C语言——菜鸟级

解题思路: gcd + 动态规划（完全背包）

注意事项: 

参考代码:

#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]); //找最大公约数，为1表示有解否则表示所有数都可以到达  
     if(s[i]<s[0]){int m=s[0];s[0]=s[i];s[i]=m;}
     
   }
 if(t==1&&s[0]!=1)//gcd判断 是否有解 为1 则这有解
 {    memset(dp,-1,sizeof(dp));t1=0;dp[0]=1;
      for(i=0;i<n;i++)
//(感觉按题目要求应该是20000000000的不过感觉也去不到那么远)*/  
      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;
 }