变量:

N - 总钱数
r - 主件的总数
p, v - 价格, 满意度(价值)的列表
对于下面例子:

p和v的格式如下,每个的第一个位置表示主件:

创建表格:

创建F为(r+1)×(N+1)的全0列表
设F[i][j] 代表(<=i)件物品时，(<=j)元的最大价值。

递推方法:

从F[i][1]到F[i][N](for i = 1~r)
即先计算只有第1个主件和其附件时,从1到j元能获得做大价值多少
再计算只有前2个主件和其附件时,从1到j元能获得做大价值多少
以此类推,按F从左到右, 从上到下的顺序。F每一行的信息从上一行获得。

F每个位置的计算方法:
取下面最大值(计算同时数组索引越界,不存在的情况需判断):
①什么都不买 ②主件 ③主件+附件a ④主件+附件b ⑤主件+附件a+附件b\

代码：

import sys
N,m,cost,satf = 0,0,{},{}
for i,line in enumerate(sys.stdin): # i 刚好是物品编号
    a = line.split()
    # print(a)
    if i==0:
        N = int(int(a[0])/10) # 总钱数
        m = int(a[1]) # 可购买物品的个数
        flag = False
    else:
        # 索引为j , 则物品编号为j+1
        price = int(int(a[0])/10) # 价格
        value = int(int(a[1])*price) # 价值
        num = int(a[2])
        if num == 0: # 对于主件, 如果没有则创建字典， 如果有则在原值左侧插入
            if cost.get(i) == None:
                cost[i] = [price]
                satf[i] = [value]
            else:
                cost[i] = [price] + cost[i]
                satf[i] = [value] + satf[i]
        else: # 对于附件, 如果没有则创建字典， 如果有则在原值右侧插入
            if cost.get(num) == None:
                cost[num] = [price]
                satf[num] = [value]
            else:
                cost[num] = cost[num] + [price]
                satf[num] = satf[num] + [value]
p = list(cost.values()) # 价格列表
v = list(satf.values()) # 价值列表
# print(p)
# print(v)
r = len(p)
F = [[0 for i in range(N+1)] for j in range(r+1)]
# F[i][j] 代表(<=i)件物品时，(<=j)元的最大价值
def decide(F,i,j,pp,vv):
    """a,b,c,d,e分别代表了5种需要比较的情况。此外, 数组索引越界则返回0
       这5个数实际上是在算: 当买的起的时候,j-price时的最大价值+value
    """
    a = F[i-1][j]
    if j-pp[0]>=0:
        b = F[i-1][j-pp[0]]+vv[0]
    else:
        b = 0
    if len(pp)>=2:
        if j-pp[0]-pp[1]>=0:
            c = F[i-1][j-pp[0]-pp[1]]+vv[0]+vv[1]
        else:
            c = 0
    else:
        return max(a,b)
    if len(pp) == 3:
        if j-pp[0]-pp[2]>=0:
            d = F[i-1][j-pp[0]-pp[2]]+vv[0]+vv[2]
        else:
            d = 0
        if j-pp[0]-pp[1]-pp[2]>=0:
            e = F[i-1][j-pp[0]-pp[1]-pp[2]]+vv[0]+vv[1]+vv[2]
        else:
            e = 0
    else:
        return max(a,b,c)
    return max(a,b,c,d,e)

for i in range(1,r+1):
    for j in range(1,N+1):
        F[i][j] = decide(F,i,j,p[i-1],v[i-1])

print(F[-1][-1]*10)