2132: 信息学奥赛一本通T1268-完全背包问题

解题思路:

注意事项:

参考代码:

m,n=map(int,input().split())
ls=[[0,0]]
for i in range(n):
    ls.append(list(map(int,input().split())))

dp=[[0 for i in range(m+1)] for j in range(n+1)]

for num in range(1,n+1):
    for wet in range(1,m+1):
        
        lis=[]
        for i in range(wet//ls[num][0]+1):
            lis.append(i*ls[num][1]+dp[num-1][wet-i*ls[num][0]])
        dp[num][wet]=max(lis)
#print(dp)
print(f"max={dp[-1][-1]}")