Cod sursa(job #2701165)
Utilizator | Varzaru Octavian Stefan tavi255 | Data | 29 ianuarie 2021 23:31:37 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | py | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
if __name__ == '__main__':
fin=open("rucsac.in","r")
fout=open("rucsac.out","w")
lines=fin.readlines()
line=lines[0]
line=line.split()
n=int(line[0])
G=int(line[1])
dp=[[0 for j in range(G+1)]for i in range(n+1)]
for i in range(1,n+1):
line=lines[i]
line=line.split()
wi=int(line[0])
value=int(line[1])
for j in range(wi,G+1):
dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+value)
fout.write(str(dp[n][G]))