转载AcWing 6. 多重背包问题 III 详解 + yxc大佬代码解读

一共 n 类物品，背包的容量是 m

每类物品的体积为v, 价值为w，个数为s

dp[i][j] 表示将前 i 种物品放入容量为 j 的背包中所得到的最大价值
dp[i][j] = max(不放入物品 i，放入1个物品 i，放入2个物品 i, … , 放入k个物品 i)
这里 k 要满足：k <= s, j - k*v >= 0

不放物品 i = dp[i-1][j]
放k个物品 i = dp[i-1][j - kv] + kw

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2v] + 2w,…, dp[i-1][j-kv] + kw)

实际上我们并不需要二维的dp数组，适当的调整循环条件，我们可以重复利用dp数组来保存上一轮的信息

我们令 dp[j] 表示容量为j的情况下，获得的最大价值
那么，针对每一类物品 i ，我们都更新一下 dp[m] –> dp[0] 的值，最后 dp[m] 就是一个全局最优值

dp[m] = max(dp[m], dp[m-v] + w, dp[m-2v] + 2w, dp[m-3v] + 3w, …)

设 m = k*v + j (0 <= j < v)，我们把 dp[0] –> dp[m] 写成下面这种形式

dp[0], dp[v], dp[2v], dp[3v], … , dp[kv]
dp[1], dp[v+1], dp[2v+1], dp[3v+1], … , dp[kv+1]
dp[2], dp[v+2], dp[2v+2], dp[3v+2], … , dp[kv+2]
…
dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[kv+j]

所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的
也就是说，dp[kv+j] 只依赖于 { dp[j], dp[v+j], dp[2v+j], dp[3v+j], … , dp[kv+j] }
其中

dp[j] = dp[j]
dp[j+v] = max(dp[j] + w, dp[j+v])
dp[j+2v] = max(dp[j] + 2w, dp[j+v] + w, dp[j+2v])
dp[j+3v] = max(dp[j] + 3w, dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v])
…
看起来很像单调队列应用里的滑动窗口的最大值，但是，这个队列中前面的数，每次都会增加一个 w ，所以我们需要做一些转换

dp[j]         =  dp[j]
dp[j+v]  -  w = max(dp[j], dp[j+v] - w)
dp[j+2v] - 2w = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w)
dp[j+3v] - 3w = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w)
...

构造 q[k] --> dp[j + k * v] - k * w 对应的队列，即可使用单调队列进行计算

每次入队的第k项值是 dp[j+kv] - kw
出队的条件是：k - s * v > q[head]

from collections import deque 

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

f = [0] * (m + 10)

for i in range(n):
    v, w, s = map(int, input().split())
    pre = list(f)

    for j in range(v):
        q = deque()
        for k in range(j, m + 1, v):
            if q and q[0] < k - s * v: 
                q.popleft()
            while q and pre[q[-1]] - (q[-1] - j) / v * w <= pre[k] - (k - j) / v * w:
                q.pop()
            q.append(k)
            f[k] = pre[q[0]] + (k - q[0]) / v * w 

print(int(f[m]))