分组背包问题

以主件为单位, 进行分组.
如果该组只有一个主件, 那么很明显, “商品”种类只有一种.
如果该组有一个主件和一个附件, 那么”商品”有2种: 1. 主件 2. 主件 + 附件(打包在了一起, 作为一个商品)
如果该组有一个主件和2个附件, 那么”商品”有4种: 1. 主件 2. 主件 + 附件1(打包在了一起, 作为一个商品) 3. 主件 + 附件2(打包在了一起, 作为一个商品) 4. 主件 + 附件1 + 附件2(打包在了一起, 作为一个商品)

很显然, 每个组只能挑选一个”商品”, 因此, 就转化为了标准的”分组背包问题”.

时间复杂度

O(N * m)

Python 代码

from collections import defaultdict

A = defaultdict(list)
B = defaultdict(list)

N, m = map(int, input().split())
for i in range(1, m + 1):
    v, p, q = map(int, input().split())
    p = v * p
    if q == 0:
        A[i].append((v, p))
    else:
        B[q].append((v, p))

for idx in A:
    for v, p in B[idx]:
        for V, P in list(A[idx]):
            A[idx].append((V + v, P + p))

dp = [0] * (N + 1)
for idx in A:
    for j in range(N, -1, -1):
        for v, p in A[idx]:
            if j >= v:
                dp[j] = max(dp[j], dp[j - v] + p)
print(dp[N])