题解 | #购物单#

# 输入：total_money为总钱数，m为可以购买物品的个数
total_money, m = map(int, input().split())

# 物品价格v，物品重要度p，物品主件附件属性q

# 单价表 Price[i] = v
Price = {}

# 价值表 Value[i] = p*v
Value = {}

# 记录主件编号
primary_key = []

# 初始化：单价表Price和价值表Value
# 三个元素为主件，附件1，附件2（题中最多有两个附件）
for i in range(m):
    Price[i] = [0, 0, 0]
    Value[i] = [0, 0, 0]

# 输入：物品价格v，物品重要度p，物品主件附件属性q
for i in range(m):
    v, p, q = map(int, input().split())
    if q == 0:
        Price[i][0] = v
        Value[i][0] = p * v
        primary_key.append(i)
    else:
        if Price[q - 1][1] == 0:
            Price[q - 1][1] = v
            Value[q - 1][1] = p * v
        else:
            Price[q - 1][2] = v
            Value[q - 1][2] = p * v

# 把构建的单价表和价值表压缩
Price_list = []
Value_list = []
for key in Price.keys():
    if key in primary_key:
        Price_list.append(Price[key])
        Value_list.append(Value[key])
# 主件的个数
primary_number = len(Price_list)

# 创建01背包问题的思考表格，行数为(主件物品数+1)，列数为(总钱数/10)+1
dp = [[0]*(int(total_money/10) + 1) for _ in range(primary_number + 1)]

total = int(total_money / 10)

for i in range(1, primary_number + 1): # 遍历每个“主件”
    P0 = Price_list[i-1][0] # 第i个主件自身的单价
    P1 = Price_list[i-1][1] # 第i个主件附件1的单价
    P2 = Price_list[i-1][2] # 第i个主件附件2的单价
    V0 = Value_list[i-1][0] # 第i个主件自身的价值
    V1 = Value_list[i-1][1] # 第i个主件附件1的价值
    V2 = Value_list[i-1][2] # 第i个主件附件2的价值
    for j in range(total + 1):
        # 什么都不买
        dp[i][j] = dp[i - 1][j]
        # 只买主件
        if 10 * j >= P0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - int(P0/10)] + V0)
        # 主件+附件1
        if 10 * j >= P0 + P1:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - int(P0/10) - int(P1/10)] + V0 + V1)
        # 主件+附件2
        if 10 * j >= P0 + P2:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - int(P0/10) - int(P2/10)] + V0 + V2)
        # 主件+附件1+附件2
        if 10 * j >= P0 + P1 + P2:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - int(P0/10) - int(P1/10) - int(P2/10)] + V0 + V1 + V2)
print(dp[primary_number][total])