蓝桥杯算法训练 最大体积 (gcd+完全背包)------C语言—菜鸟级

/*问题描述
　　每个物品有一定的体积（废话），不同的物品组合，装入背包会战用一定的总体积。
假如每个物品有无限件可用，那么有些体积是永远也装不出来的。为了尽量装满背包，
附中的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;
 } 

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/79951813