多重背包问题有三种解法，朴素解法时间复杂度过高O(N^3)，基本不太用，基于二进制优化和基于单调队列优化的版本时间复杂度比较低，实际应用较多
朴素解法
import sys
sys.stdin = open('./data.txt', 'r')'''
多重背包 N^3 解法状态转移
dp(i, j)表示前i个物品在容量是j的情况下的最大总价值cost[i] 表示物品开销
val[i] 表示物品价值
max_cnt[i] 表示物品i最多能够取的个数dp(i, j) = max {dp(i-1, j),dp(i-1, j - cost[i]) + val[i], dp(i-1, j - cost[i]*2) + val[i]*2,......dp(i-1, j - cost[i]*k) + val[i]*k,
}其中k满足 cost[i]*k < max_cnt[i]'''dp = [[0 for _ in range(110)] for _ in range(110)]
arr = []
N, V = map(int, input().split())
for _ in range(N):v, w, s = map(int, input().split())arr.append((v, w, s))for i in range(N):for j in range(V+1):max_cnt = min(arr[i][2], j // arr[i][0])if i == 0:dp[i][j] = arr[i][1] * max_cntelse:dp[i][j] = dp[i-1][j]for k in range(1, max_cnt + 1):dp[i][j] = max(dp[i][j], dp[i-1][j - k * arr[i][0]] + k * arr[i][1])
print(dp[N-1][V])
二进制优化版本
import sys
sys.stdin = open('./data.txt', 'r')'''
多重背包 N*V*Log(N) 解法每个物品都有一个最大的数量S 把这个S拆成二进制的额组合，例如最多选10个物品，可以把0-10这些数看做1 2 4 3 这几个数的选或者不选的组合，这样把分组背包问题转成一个01背包问题 '''dp = [[0 for _ in range(110)] for _ in range(110)]
arr = []
N, V = map(int, input().split())
for _ in range(N):v, w, s = map(int, input().split())base = 1while s >= base:arr.append( (v*base, w*base) )s -= basebase *= 2if s != 0:arr.append((v * s, w * s))dp = [0] * (V + 1)for i in range(len(arr)):for j in range(V, -1, -1):if i == 0:dp[j] = arr[i][1] if j >= arr[i][0] else 0else:if j >= arr[i][0]:dp[j] = max(dp[j], arr[i][1] + dp[j - arr[i][0]])print(dp[V])
单调队列优化版本
import sys
sys.stdin = open('./data.txt', 'r')'''
单调队列优化的多重背包
dp(i, j) 表示前i种物品做选择，总容量为j时候的最大总价值ci 表示物品i的开销
wi 表示物品i的价值
si 表示物品i能够选的数量上限递推公式有如下关系
dp(i,j) = max{ dp(i-1, j), dp(i-1, j-ci*1) + wi*1, dp(i-1, j-ci*2) + wi*2, dp(i-1, j-ci*3) + wi*3 ........ dp(i-1, j-ci*si) + wi*si }
dp(i,j-ci) = max{ dp(i-1, j-ci*i), dp(i-1, j-ci*2) + wi*1, dp(i-1, j-ci*3) + wi*2 ........ dp(i-1, j-ci*si) + wi*(si-1), dp(i-1, j-ci*(si+1) ) + wi*si}观察dp(i, j) 相对于dp(i, j-ci)的变化，其实是一个长度不超过si + 1的滑动窗口在移动，窗口里面的值每滑动一次就要增加wi，
只要知道了dp(i, j-ci) 就可以套用滑动窗口的原理，求出dp(i, j) 在i固定的一行dp数值求解里面，其实是ci个窗口在滑动，起点分别是0， 1， 2 .... ci-1每过一轮窗口滑动，窗口中的数值需要全部加wi, 实际上只需要记录每个元素进入单调队列的时间戳，
根据时间戳和当前滑动的轮数的差值就知道这个数值需要加上多少个wi , 不是真的每一轮都要把wi加到单调队列的数值上面'''from collections import dequearr = []
N, V = map(int, input().split())
for _ in range(N):v, w, s = map(int, input().split())arr.append((v, w, s))dp = [[0] * (V + 1) for _ in range(N)]for i in range(N):# 开销，价值，最大数量ci, wi, si = arr[i]if i == 0:for j in range(V + 1):cnt = min(j // ci, si)dp[i][j] = cnt * wielse:for window_start in range(0, min(V, ci)):dp[i][window_start] = dp[i - 1][window_start]que = deque()que.append((dp[i - 1][window_start], 0)) # [入队数值，入队时间戳]time_cnt = 0for j in range(window_start + ci, V + 1, ci):time_cnt += 1# 删除过期数据while len(que) > 0 and time_cnt - que[0][1] >= si + 1:que.popleft()while len(que) > 0 and que[-1][0] + (time_cnt - que[-1][1]) * wi <= dp[i - 1][j]:que.pop()que.append((dp[i - 1][j], time_cnt))dp[i][j] = que[0][0] + (time_cnt - que[0][1]) * wiprint(dp[N - 1][V])