题解 | 购物单

import sys

# 1、把物品分类：主品，附件，分别存储它们对应的价格、满意度。把所有价格下的满意度用列表dp存储
almoney, alquantity = map(int, input().split())
main_products, accessories = {}, {}
for i in range(1, alquantity + 1):
    val, importance, clas = map(int, input().split())
    if clas == 0:
        main_products[i] = [val, val * importance]
    else:
        if clas in accessories:
            accessories[clas].append([val,val * importance])
        else:
            accessories[clas] = [[val, val * importance]]

dp = [0] * (almoney + 1)
# 2、列出每一个主件的价格和满意度。用列表存储：不带附件时、带1个、带2个附件时的价格和满意度
for k, v in main_products.items():
    va = []
    satisfaction = []
    # k是名称，v[0]是单价，存储到va列表中。v[1]是满意度
    va.append(v[0])
    satisfaction.append(v[1])
    # 如果k有附件
    if k in accessories:
        # 那就让单价加上附件1（也就是[k][0]的单价  va是单价
        va.append(va[0] + accessories[k][0][0])
        satisfaction.append(satisfaction[0] + accessories[k][0][1])

        if len(accessories[k]) > 1:
            va.append(va[0] + accessories[k][1][0])
            satisfaction.append(satisfaction[0] + accessories[k][1][1])
            va.append(va[0] + accessories[k][0][0] + accessories[k][1][0])
            satisfaction.append(
                satisfaction[0] + accessories[k][0][1] + accessories[k][1][1]
            )
    # 3、遍历能出的金额-从高到低
    for i in range(almoney, -1, -10):
        # 对于不同的组合，如果金额>该物品及其附件的价格
        for key, n in enumerate(va):
            if i - va[key] >= 0:
                #花该价钱的最大满意度=没买当前商品时的最大满意度+买这个商品的满意度
                dp[i] = max(dp[i], dp[i - va[key]] + satisfaction[key])

print(dp[almoney])