试题 算法训练 最大体积（动态规划）

问题描述
　　每个物品有一定的体积（废话），不同的物品组合，装入背包会战用一定的总体积。假如每个物品有无限件可用，那么有些体积是永远也装不出来的。为了尽量装满背包，附中的OIER想要研究一下物品不能装出的最大体积。题目保证有解，如果是有限解，保证不超过2，000，000，000
　　如果是无限解，则输出0
输入格式
　　第一行一个整数n（n<=10），表示物品的件数
　　第2行到N+1行: 每件物品的体积(1<= <=500)
输出格式
　　一个整数ans，表示不能用这些物品得到的最大体积。
样例输入
3
3
6
10
样例输出
17
思路：
此题的意思就是在物品中背包保证不超过2，000，000，000的容量的情况下找到不能用这些物品得到的最大体积。那我们就分为两种情况考虑：
如果所有的物品体积的最大公约数不为1，则为无限解；
如果所有的物品体积的最大公约数为1，则从无限大开始，找出第一个不能组成的数。
我们知道如果最大公约数不为1的话不能用这些物品得到的最大体积是无线大的数，但公约数为1的话可以找到最大值因为每件物品的体积小于等于500。
那我们就先计算出所有的物品体积的最大公约数。
然后在用一个列表存储所有的物品体积对应可以存储的容量我们标记为1.用vla[i]对应i表示是否可以用以上物品装满可以为1.
然后在从大到小遍历vla找打最大的容量。
程序：

def gcd(a,b):  #2个数的最大公约数
    if a%b==0:
        return b
    return gcd(b,a%b)
def zgcd(c):  #遍历所有物品求最大公约数
    t=c[0]
    for i in range(1,n):
        t=gcd(t,c[i])
    return t
def maxt(a,n):  #找出不能用这些物品得到的最大体积
    vla=[0 for i in range(200002)]  #标记列表
    vla[0]=1  #初始化
    for i in range(n):  #当前物品
        for j in range(a[i],200001):  #当前容量
            if vla[j-a[i]]==1:  #是否可以装满
                vla[j]=1  
    for i in range(200000,-1,-1):  #遍历val找出最大容量
        if vla[i]==0:
            print(i)
            return 0
    print(0)
        
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))  #存储物品
z=zgcd(a)
if z==1:  #是否最公约数为1，表示可以找到最大容量
    maxt(a,n)
else:  #公约数不为1
    print(0)

禁止转载。仅用于自己学习。对程序错误不负责。