题解 | #购物单#

basic = list(map(int, input().split()))
N = basic[0]
items = []
for _ in range(basic[1]):
    items.append(list(map(int, input().split())))
for i in range(len(items)):
    if items[i][2]:
        items[items[i][2] - 1].append(items[i][:])
        items[i] = []
dp = [0] * (N + 1)
for itm in items:
    if itm:
        val = itm[0]
        satis = itm[1]
        if len(itm) == 3:
            for i in range(N, -1, -1):
                if val <= i:
                    dp[i] = max(dp[i], dp[i - val] + val * satis)
        if len(itm) > 3:
            dp_se = dp[:]
            for i in range(N, -1, -1):
                if val <= i:
                    dp_se[i] = dp[i - val] + val * satis  # 选择第i件物品
            for i in range(3, len(itm)):
                val_a = itm[i][0]
                w = itm[i][1]
                for j in range(N, -1, -1):
                    if val_a + val <= j:
                        dp_se[j] = max(dp_se[j], dp_se[j - val_a] + val_a * w)
            dp = [max(dp[i], dp_se[i]) for i in range(len(dp))]
print(dp[-1])

先把附属的物件加入进真正的物件中，在进行01背包的时候判断是否有附属物件，如果有的话就新增一个矩阵判断取的情况，最后再判断不增加和增加物件的dp向量的大小