多重背包问题III
单调队列优化
时间复杂度: $O(N*V)$
python 代码
from collections import *
N, V = map(int, input().split())
dp = [0 for i in range(V + 1)]
for i in range(N):
v1, w1, s1 = map(int, input().split())
g = dp[:] # 滚动数组 将上一层状态复制
for j in range(v1): # 枚举余数
q = deque() # 定义单调队列 存储前个s(物品数量)中的最大值 队列中的元素单调递减
for k in range(j, V+1, v1):
if q and k - q[0] > v1 * s1: # 如果队头到当前的物品的数量大于s个 队头出队
q.popleft()
"""
dp[j] = g[j]
dp[j+v] = max(g[j], g[j+v] - w) + w
dp[j+2v] = max(g[j], g[j+v] - w, g[j+2v] - 2w) + 2w
dp[j+3v] = max(g[j], g[j+v] - w, g[j+2v] - 2w, g[j+3v] - 3w) + 3w
这样,每次入队的值是 g[j+k*v] - k*w 将队尾小于等于的值弹出
表达式为 g[q[-1]] - (q[-1] - j) // v * w <= g[k] - (k - j) // v * w
"""
while q and g[q[-1]] + (k - q[-1]) // v1 * w1 <= g[k]: #化简表达式 不化简可能超时
q.pop()
q.append(k)
#为化简前 dp[k] = max(dp[k], g[q[0]] - (q[0] - j) // v1 * w1 + (k - j) // v1 * w1)
dp[k] = max(dp[k], g[q[0]] + (k - q[0]) // v1 * w1)
k += v1
print(dp[V])