题解 | 购物单

import sys
from math import gcd
from functools import reduce

a = []
for line in sys.stdin:
    a.append(list(map(int,line.split()))) # 将列表中元素由字符串转换为整型
    # print(int(a[0]) + int(a[1]))
# print(a)

num = a[0][1] # 物品数量
budget = a[0][0] # 预算
total_list = a[1:] # 物品价格、重要度、主件编号
# print(total_list)

price_list = [item[0] for item in total_list]
# print(price_list)
step = reduce(gcd, price_list) # 求最大公约数
# print(len)
min_price = min(price_list)
# print(min_price)

# #DP表初始化
# dp = [[0]*(budget//len+1) for _ in range(num+1)]

goods = {}  # 主件编号 -> [主件, 附件1, 附件2]
for i, (v, p, q) in enumerate(total_list):
    if q == 0:
        if (i + 1) not in goods:
            goods[i + 1] = [] # 初始化
        goods[i + 1].insert(0, (v, p))  # 主件插入到第一个位置
    else:
        if q not in goods:
            goods[q] = []  # 占位主件（防止主件之后出现）
        goods[q].append((v, p))
# print(goods)
# dp[j] 表示预算j下的最大满意度
dp = [0] * (budget//step + 1)

for group in goods.values():
    v0, p0 = group[0]
    # v1, p1 = group[1]
    # v2, p2 = group[2] 
    w = []  # 放置所有组合 (cost, value)
    w.append((v0, v0*p0))
    if len(group) >= 2: # 1个附件，共两种组合
        v1, p1 = group[1]
        w.append((v0 + v1, v0*p0 + v1*p1))
    if len(group) >= 3: # 2个附件，共四种组合
        v1, p1 = group[1]
        v2, p2 = group[2]
        w.append((v0 + v2, v0*p0 + v2*p2))
        w.append((v0 + v1 + v2, v0*p0 + v1*p1 + v2*p2))
    # print(w)
    # 0-1 背包核心循环（逆序）
    for j in range(budget, 0, -step):
        for cost, val in w:
            if j >= cost:
                dp[j//step] = max(dp[j//step], dp[(j - cost)//step] + val)

print(dp[budget//step])