题解 | #购物单#

'''
解题思路：
动态规划：带条件的0-1背包问题
'''
#==========================================
# 读入原始数据，背包数除10

w_max,n = map(int,input().strip().split())
w_max = w_max//10
#print('w_max=',w_max,'n=',n)
T = []
for i in range(n):
    v,w,q = map(int,input().strip().split())
    T.append([v//10,w*v//10,q])
#print('T=',T)

#==========================================
# 处理主件

W = [[] for _ in range(n)]
V = [[] for _ in range(n)]
I = []
for i in range(n):
    if T[i][2]==0:
        W[i].append(T[i][0])
        V[i].append(T[i][1])
        I.append(i)
#print('W=',W)
#print('V=',V)
#print('I=',I)

#==========================================
# 处理附件

for i in range(n):
    if T[i][2]>0:
        ii = T[i][2]-1
        W[ii].append(T[i][0])
        V[ii].append(T[i][1])
#print('W=',W)
#print('V=',V)

#==========================================
# 附件的排列组合

for i in range(n):
    if len(W[i])==2:
        W[i] = [W[i][0], W[i][0]+W[i][1]]
        V[i] = [V[i][0], V[i][0]+V[i][1]]
    if len(W[i])==3:
        W[i] = [W[i][0], W[i][0]+W[i][1], W[i][0]+W[i][2], W[i][0]+W[i][1]+W[i][2]]
        V[i] = [V[i][0], V[i][0]+V[i][1], V[i][0]+V[i][2], V[i][0]+V[i][1]+V[i][2]]
#print('W=',W)
#print('V=',V)

#==========================================

DP = [[0]*(w_max+1) for _ in range(len(I)+1)]
for i in range(1,len(I)+1):
    ii = I[i-1]
    for j in range(1,w_max+1):
        t_max = DP[i-1][j]
        for k in range(len(W[ii])):
            W_i = W[ii][k]
            V_i = V[ii][k]        
            if j>=W_i:
                t_max = max(t_max, DP[i-1][j-W_i]+V_i)
        DP[i][j] = t_max
#print('DP=',DP)    
print(DP[-1][-1]*10) 


#=================================================================================

'''
# https://blog.csdn.net/qq_38410730/article/details/81667885

n = 4
w_max = 8
W = [0,2,3,4,5]
V = [0,3,4,5,6]

DP = [[0]*(w_max+1) for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, w_max+1):
        if j<W[i]:
            DP[i][j] = DP[i-1][j]
        else:
            DP[i][j] = max(DP[i-1][j], DP[i-1][j-W[i]]+V[i])

print(DP[n][w_max])

select = []
j = w_max
for i in range(n,0,-1):
    if DP[i][j]>DP[i-1][j]:
        select.append(i)
        j = j-W[i]
print(select)
'''
#===============================================================