多重背包问题 python题解

n,m=map(int,input().split())

W=[]

V=[]

#转化为01背包问题，同时减少重复的数据，降低时间复杂度

for i in range(n):

    a,b,c=map(int,input().split())

    q=min(m//a,c)

    p=1

    while q>p:

        W.append(a*p)

        V.append(b*p)

        q-=p

        p*=2 

    W.append(a*q)

    V.append(b*q)

#同01背包解法

n=len(W)

dp=[0]*(m+1)

for i in range(n):

    for j in range(m,W[i]-1,-1):

        dp[j]=max(dp[j],dp[j-W[i]]+V[i])

print(dp[m])