题解 | #购物单#

抄作业真相，leetcode太卷了，还是牛客刷题有感觉

money,capacity = map(int ,input().split(" "))
money //=10
weight = [[0]*3 for _ in range(capacity+1)]
satisfaction = [[0]*3 for _ in range(capacity+1) ]
answer = [[0]*(money+1) for _ in range(capacity+1)]
for i in range(1,capacity+1):
    price,importance,primary = map(int,input().split())
    price //= 10
    if primary==0:
        weight[i][0]=price
        satisfaction[i][0]=price*importance
    elif weight[primary][1]==0:
        weight[primary][1]=price
        satisfaction[primary][1]=price*importance
    else:
        weight[primary][2]=price
        satisfaction[primary][2]=price * importance
        
for i in range(1,capacity+1):
    for j in range(0,money+1):
        if j >= weight[i][0]:
            answer[i][j]=max(answer[i-1][j],answer[i-1][j-weight[i][0]]+satisfaction[i][0])
            if j >= weight[i][0]+weight[i][1]:
                answer[i][j]=max(answer[i][j],answer[i-1][j-weight[i][0]-weight[i][1]]+satisfaction[i][0]+satisfaction[i][1])
            if j >= weight[i][0]+weight[i][2]:
                answer[i][j]=max(answer[i][j],answer[i-1][j-weight[i][0]-weight[i][2]]+satisfaction[i][0]+satisfaction[i][2])
                if j >= weight[i][0]+weight[i][2]+weight[i][1]:
                    answer[i][j]=max(answer[i][j],answer[i-1][j-weight[i][0]-weight[i][2]-weight[i][1]]+satisfaction[i][0]+satisfaction[i][2]+satisfaction[i][1])
        else:
            answer[i][j] = answer[i-1][j]
print(answer[capacity][money]*10)