2134: 信息学奥赛一本通T1270-混合背包

解题思路:

注意事项:

参考代码:

m,n=map(int,input().split())
ls=[[0,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):
        if wet < ls[num][0]:
            dp[num][wet]=dp[num-1][wet]
        else:
            if ls[num][2]>0:
                if wet//ls[num][0] >=ls[num][2]:
                    lis=[]
                    for i in range(ls[num][2]+1):
                        lis.append(i*ls[num][1]+dp[num-1][wet-i*ls[num][0]])
                    dp[num][wet]=max(max(lis),dp[num-1][wet])
                else:
                    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(max(lis),dp[num-1][wet])
            else:
                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[-1][-1])