题解 | #购物单#

All, num = map(int, input().split())

pri, attach ={}, {}

#  现在要计算主件和附件，并纳入字典中，这部分是input的

for i in range(1, num+1):
    
    [v, p, q] = map(int, input().split())

    if q == 0:    # 只有主件
       pri[i] = [v, p]
    else:
       if q in attach:
          attach[q].append([v, p])   #存在2个附件

       else:
          attach[q] = [[v, p]]    #存在1个附件

#  之后开始计算w[i][k]和v[i][k], i代表物品的编号，k代表附件的情况，分为四种;0,1,2,12

# 
w = [[]]
v = [[]]

for key in pri:
    w_temp = []
    v_temp = []
    w_temp.append(pri[key][0])    # 第1种情况，只有主件
    v_temp.append(pri[key][0]*pri[key][1])
    if key in attach:  
        w_temp.append(w_temp[0]+attach[key][0][0])
        v_temp.append(v_temp[0]+attach[key][0][0]*attach[key][0][1])   # 第2种，主件+附件1
        if len(attach[key]) > 1:
          w_temp.append(w_temp[0]+attach[key][1][0])
          v_temp.append(v_temp[0]+attach[key][1][0]*attach[key][1][1])   # 第3种，主件+附件2
          w_temp.append(w_temp[0]+attach[key][1][0]+attach[key][0][0])
          v_temp.append(v_temp[0]+attach[key][1][0]*attach[key][1][1]+attach[key][0][0]*attach[key][0][1])   # 第4种，主件+附件1+附件2
    w.append(w_temp)
    v.append(v_temp)

#  最后一步就是带入背包的公示了
#  行，代表物品的编号，即这里主件的个数编号
#  列，代表总的容量，即这里的总价格，All
#  标准的公式为m行 n列

n = All
m = len(pri)

dp = [[0]*(n+1) for _ in range(m+1)]

for i in range(1, m+1):
    for j in range(10, n+1, 10):

        max1 =  dp[i-1][j]

        for k in range(len(w[i])):
                 
            if j-w[i][k] >= 0:
                max1 = max(max1, dp[i-1][j-w[i][k]]+v[i][k])
            
        dp[i][j] = max1

print(dp[m][n])