前言

找了这么多竟然没有找到python的题解，这里补充一下直接用队列的python写法

import collections
N = 20001
dp = [0] * N
[n, m] = map(int, input().split())
q = collections.deque()
for i in range(n):
    [v, w, s] = map(int,input().split())
    for j in range(v):
        q.clear()  # 注意每次新的循环都需要初始化队列
        num = (m-j)//v  # 剩余的空间最多还能放几个当前物品
        for k in range(0,num+1):
            val = dp[k*v+j]-k*w
            while q and val >= q[-1][1]:
                q.pop()
            q.append([k,val])
            if q[0][0] < k-s:  # 存放的个数不能超出物品数量，否则弹出
                q.popleft()
            dp[v*k+j] = q[0][1]+k*w)
print(dp[m])

第一次写题解，欢迎大佬们给出意见