题解 | 购物单

"""
 @Author: Nut
 @FileName: emmm.py
 @DateTime: 2025/8/9 16:44
 @SoftWare: PyCharm
"""
import sys
from itertools import combinations

# 输入
n, m = map(int, sys.stdin.readline().strip().split())
info = []
for _ in range(m):
    info.append(list(map(int, sys.stdin.readline().strip().split())))

# [主件(v,w),[附件1(v,w)，附件2(v,w)]]
temp = [[None, []] for i in range(m)]
# [[主件(v,w*v)，主件+附1(v,w*v)，主+附2(v,w*v)，主+附1+附2(v,w*v)]]
weight = []

for obj_idx in range(m):
    if info[obj_idx][2] == 0:
        temp[obj_idx][0] = (info[obj_idx][0], info[obj_idx][1])
    else:
        temp[info[obj_idx][2] - 1][1].append((info[obj_idx][0], info[obj_idx][1]))

for idx, (main, ass) in enumerate(temp):
    # 存在主件
    if main:
        w = [(main[0], main[0] * main[1])]
        for r in range(1, len(ass) + 1):
            for attch in combinations(ass, r):
                w.append(
                    (
                        main[0] + sum([v[0] for v in attch]),
                        main[0] * main[1] + sum([v[0] * v[1] for v in attch]),
                    )
                )
        weight.append(w)

# 背包问题：dp[i][j]:前 i 个商品，预算为 j 时的最大价值
# dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]])
item_count = len(weight)

dp = [[0] * (n + 1) for _ in range(item_count + 1)]
for i in range(1, item_count + 1):  # 物品
    for j in range(1, n + 1):  # 预算
        for v, w in weight[i - 1]:
            if v <= j:
                # 选拿或不拿
                dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i - 1][j - v] + w)
            else:
                # 不能拿
                dp[i][j] = max(dp[i][j], dp[i - 1][j])

print(dp[item_count][n])

真吐了简直是石山下辈子再也不学计算机了