题解 | #购物单#

N, m = list(map(int, input().split()))
main = dict()
appendlis = dict()              
for i in range(1, m+1):
    v, p, q = list(map(int,input().split()))
    if q == 0:
        main[i] = [v, v*p]
    elif q in appendlis:
        appendlis[q].append([v, v*p])
    else:
        appendlis[q] = [[v, v*p]]       #将同一个主件的所有附件的（价格，满意度）放到一个字典里
 
 
dp = [0] * (N+1)                    #创建长度为 N+1 的列表
for key, value in main.items():     #遍历字典的一条
    w = []
    v = []
    w.append(value[0])      #分别是[v, v*p]
    v.append(value[1])
    if key in appendlis:    #有附件的情况（我们就加上最多2的三次方的情况）
        w.append(w[0] + appendlis[key][0][0])       #为价格表加上主件+附件1的价格
        v.append(v[0] + appendlis[key][0][1])       #主件+附件1的满意度
        if len(appendlis[key]) == 2:                #如果还有第二件
            w.append(w[0]+appendlis[key][1][0])     #主件+附件2的价格
            v.append(v[0]+appendlis[key][1][1])     #主件+附件2的满意度
            w.append(w[0]+appendlis[key][0][0]+appendlis[key][1][0])    #主件+附件1的+附件2价格
            v.append(v[0]+appendlis[key][0][1]+appendlis[key][1][1])    #主件+附件1的+附件2满意度
    for i in range(N, -1, -10):         #在可有价格内步长-10进行遍历,
        for k in range(len(w)):         #必有主件的情况下和附件1，2的结合价格情况1-4种
            if i >= w[k]:               #当所有金额大于买这种主+附的价格时（背包容纳能够容纳这种组合）
                dp[i] = max(dp[i], dp[i-w[k]] + v[k])       #理解为一一给组合价格之上的dp数组赋上目前最大的满意度，再与之后的比较。之前dp[i]都是0，我们只赋值了10步长里的
                                                            #而且在第一组主附件组合中只负担得起单独买主件800，第一次i只能循环这一次

print(dp[N])

研究评论区大佬的代码的注释，想循环少一点要的就是CPU烧干。