题解 | #购物单#

import sys
money,num = map(int,input().split(" "))   ##钱和商品数
money = int(money/10)   ##由于钱都是10的倍数，故除以10减少后续循环次数
W = {}  ##初始化价钱（重量）的字典
V = {}  ##初始化满意度（价格）的字典
main_key = []  ##初始化主键编号
###原始数据中的编号q标识物品为主件还是附件
###现在要将物品的价钱和满意度分别形成两个[[主件,附件,附件],...]形式的矩阵，而原始的附件数据则置为[0,0,0]，后###续在计算过程中将被舍弃。商品数减少为[主件,附件,附件]形式的套装数。
for i in range(1,num+1): ###价钱W和满意度V，初步设计为num*3的矩阵(字典形式)。注意：没有W.keys()==0 
    W[i] = [0,0,0]
    V[i] = [0,0,0]
for i in range(1,num+1): ###读入具体的商品数据
    v,p,q = list(map(int,input().split(" ")))
    if q == 0:  ###q==0代表该商品为主件，0号位置为其数据，则如总价一样，将物品单价除以10，同时记录到主件目录
        W[i][0] = int(v/10)
        V[i][0] = int(v*p/10)
        main_key.append(i)
    else:   ###q!=0代表该商品为附件
        if W[q][1] == 0: ##通过序号q找到相应主件，如果主件行没有挂载附件，则将当前附件挂入1号位，单价除以10
            W[q][1] = int(v/10)
            V[q][1] = int(v*p/10)
        else:    ##通过序号q找到相应主件，如果主件已挂载1个附件，则将当前附件挂入2号位置，单价除以10
            W[q][2] = int(v/10)
            V[q][2] = int(v*p/10)
        ##由于题目中说明了最多只有2个附件，所以分支到此结束。如果附件更多，则需要更多分支。
wlist = [] ##初始化主件价钱wlist，此时包含附件的[0,0,0]数据。此是列表，从0开始。
vlist = [] ##初始化住键满意度vlist，此时包含附件的[0,0,0]数据。此是列表，从0开始。
for key in W.keys():  
    if key in main_key:    ##main_key中包含所有主件条目编号，仅保留W和V中的主件。
        wlist.append(W[key])
        vlist.append(V[key])
m = len(wlist)  ##记录主件数据条数，即前边说的套装数。
dp = [[0]*(money+1) for _ in range(m+1)] ##money+1行是因为最上边有一行0，m+1列是因为最左边有一列0
for i in range(1,m+1):  ##件数从少到多遍历，从1开始到m个。
    w1 = wlist[i-1][0]  ##价钱矩阵的第i行(wlist是矩阵，编号从0开始)：主件价钱
    w2 = wlist[i-1][1]  ##价钱矩阵的第i行(wlist是矩阵，编号从0开始)：1号附件价钱
    w3 = wlist[i-1][2]  ##价钱矩阵的第i行(wlist是矩阵，编号从0开始)：2号附件价钱
    v1 = vlist[i-1][0]  ##满意度矩阵的第i行(vlist是矩阵，编号从0开始)：主件满意度
    v2 = vlist[i-1][1]  ##满意度矩阵的第i行(vlist是矩阵，编号从0开始)：1号附件满意度
    v3 = vlist[i-1][2]  ##满意度矩阵的第i行(vlist是矩阵，编号从0开始)：2号附件满意度
    for j in range(money,-1,-1):  ##钱数从多到少遍历，从money到0。从少到多也行。对于i件物品时，j的取值不会##互相影响。对于用j元买第i件物品，现在主件需要w1元，计算的逻辑是：比较《已购买的i-1件物品目标值(j-w1元和w1元##都用于购买之前的i-1件物品)》和《j-w1元能实现的目标值+把j元中的w1元用于第i件物品的w1元产生的满意度v1之和》。##其他附件的比较同理。
        dp[i][j] = dp[i-1][j]   ##先将上一行的目标值取出
        if j-w1 >= 0:  ##如果够买第i个主件，则比较w1元用于主件i更好还是之前的i-1件更好
            dp[i][j] = max(dp[i][j],dp[i-1][j-w1]+v1)
        if j-w1-w2 >= 0: ##如果够买第i个主件和第i个1号附件，则比较w1+w2元用于主件i更好还是之前的i-1件更好
            dp[i][j] = max(dp[i][j],dp[i-1][j-w1-w2]+v1+v2)
        if j-w1-w3 >= 0: ##如果够买第i个主件和第i个2号附件，则比较w1+w3元用于主件i更好还是之前的i-1件更好
            dp[i][j] = max(dp[i][j],dp[i-1][j-w1-w3]+v1+v3)
        if j-w1-w2-w3 >= 0: ##如果第i个主件和全部附件都购买，则比较总价w1+w2+w3用于此处还是之前
            dp[i][j] = max(dp[i][j],dp[i-1][j-w1-w2-w3]+v1+v2+v3)
print(int(dp[m][money]*10)) ##最终在money元时购买m件套装的目标值就是最终结果。