試題 算法訓(xùn)練 最大體積（動(dòng)態(tài)規(guī)劃）

問題描述
　　每個(gè)物品有一定的體積（廢話），不同的物品組合，裝入背包會(huì)戰(zhàn)用一定的總體積。假如每個(gè)物品有無(wú)限件可用，那么有些體積是永遠(yuǎn)也裝不出來(lái)的。為了盡量裝滿背包，附中的OIER想要研究一下物品不能裝出的最大體積。題目保證有解，如果是有限解，保證不超過2，000，000，000
　　如果是無(wú)限解，則輸出0
輸入格式
　　第一行一個(gè)整數(shù)n（n<=10），表示物品的件數(shù)
　　第2行到N+1行: 每件物品的體積(1<= <=500)
輸出格式
　　一個(gè)整數(shù)ans，表示不能用這些物品得到的最大體積。
樣例輸入
3
3
6
10
樣例輸出
17
思路：
此題的意思就是在物品中背包保證不超過2，000，000，000的容量的情況下找到不能用這些物品得到的最大體積。那我們就分為兩種情況考慮：
如果所有的物品體積的最大公約數(shù)不為1，則為無(wú)限解；
如果所有的物品體積的最大公約數(shù)為1，則從無(wú)限大開始，找出第一個(gè)不能組成的數(shù)。
我們知道如果最大公約數(shù)不為1的話不能用這些物品得到的最大體積是無(wú)線大的數(shù)，但公約數(shù)為1的話可以找到最大值因?yàn)槊考锲返捏w積小于等于500。
那我們就先計(jì)算出所有的物品體積的最大公約數(shù)。
然后在用一個(gè)列表存儲(chǔ)所有的物品體積對(duì)應(yīng)可以存儲(chǔ)的容量我們標(biāo)記為1.用vla[i]對(duì)應(yīng)i表示是否可以用以上物品裝滿可以為1.
然后在從大到小遍歷vla找打最大的容量。
程序：

def gcd(a,b):  #2個(gè)數(shù)的最大公約數(shù)
    if a%b==0:
        return b
    return gcd(b,a%b)
def zgcd(c):  #遍歷所有物品求最大公約數(shù)
    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)]  #標(biāo)記列表
    vla[0]=1  #初始化
    for i in range(n):  #當(dāng)前物品
        for j in range(a[i],200001):  #當(dāng)前容量
            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()))  #存儲(chǔ)物品
z=zgcd(a)
if z==1:  #是否最公約數(shù)為1，表示可以找到最大容量
    maxt(a,n)
else:  #公約數(shù)不為1
    print(0)

禁止轉(zhuǎn)載。僅用于自己學(xué)習(xí)。對(duì)程序錯(cuò)誤不負(fù)責(zé)。