题解 | #购物单# 背包问题 状态转移矩阵

'''
背包问题：体积V，i种物品，物品体积w(i)物品价值v，求背包能容纳下的物品最大价值。
f[i][j]=max{f[i-1][j],f[i-1][j-w(i)]+v(i)}
f[i][j]:从i个物品中选取，能放入体积为j的背包的最大价值
两种选择：第i个物品放不进体积为j的背包，最大价值为f[i-1][j]
         第i个物品放得进体积为j的背包(j>w(i))，最大价值为f[i-1][j-w(i)]+v(i)
最后简化到基准f[0][...]=0
            f[...][0]=0
'''

num=input().split()
N=int(num[0])
m=int(num[1])
main={}  #主件
annex={} #附件
for i in range(1,m+1):
    x,y,z=map(int,input().split())
    if z==0: # 主件
        main[i]=[x,y]
    else:    # 附件
        if z in annex:
            annex[z].append([x,y])
        else:
            annex[z]=[[x,y]]

m=len(main)

v=[[]] #价格
s=[[]] #满意度=价格*重要度
for key in main:
    v0,s0=[],[]  # 临时记录表
    v0.append(main[key][0])
    s0.append(main[key][0]*main[key][1])
    if key in annex.keys(): 
        # 附件对应的主件存在（主件、主件+附件1、主件+附件2、主件+附件1+附件2）
        v0.append(v0[0]+annex[key][0][0])  #主件+附件1
        s0.append(s0[0]+annex[key][0][0]*annex[key][0][1])
        if len(annex[key])>1:
            v0.append(v0[0]+annex[key][1][0])  #主件+附件2
            s0.append(s0[0]+annex[key][1][0]*annex[key][1][1])
            v0.append(v0[0]+annex[key][0][0]+annex[key][1][0]) #主件+附件1+附件2
            s0.append(s0[0]+annex[key][0][0]*annex[key][0][1]+annex[key][1][0]*annex[key][1][1])
    v.append(v0)
    s.append(s0)
#print(v)
#print(s)
# 状态转移方程
dp=[[0]*(N+1) for _ in range(m+1)]
#print(len(dp[0]))
for i in range(1,m+1):
    for j in range(10,N+1,10): 
        #每件物品的价格(都是 10 元的整数倍),N元以内的最大满意度，所构成的最终金额必定是10 的倍数
        max_i=dp[i-1][j]
        for k in range(len(v[i])):
            if j-v[i][k]>=0:
                max_i=max(max_i,dp[i-1][j-v[i][k]]+s[i][k])
        dp[i][j]=max_i

print(dp[m][N])
#print(dp)