题解 | #购物单#

n,m=map(int,input().split())
obj={}
base=10//因为全是10的倍数，所以把金额除以10以减少运算量
sum=int(n/base)
for i in range(1,m+1)://这里是把对应的主附件的价格及满意度保存在字典中
    x,y,z=map(int,input().split())
    if z:
        if z in obj:
            obj[z]=obj[z]
        else:
            obj[z]=[]
        obj[z].append([int(x/base),(int(x/base))*y])
    else:
        if i in obj:
            obj[i]=obj[i]
        else:
            obj[i]=[]
        obj[i].insert(0,[int(x/base),(int(x/base))*y])
lst=list(obj.values())//将字典的值转为数组
dp=[0]*(sum+1)
for i in lst://遍历lst数组
    p,v=[],[]
    p.append(i[0][0])
    v.append(i[0][1])
    if len(i)>1://如果有附件则将附件的价值及满意度加上主件的价值及满意度添加到数组中
        p.append(i[0][0]+i[1][0])
        v.append(i[0][1]+i[1][1])
    if len(i)>2://如果有两个附件则将第二个附件的价值及满意度加上主件的价值及满意度添加到数组中
        p.append(i[0][0]+i[2][0])
        v.append(i[0][1]+i[2][1])
        p.append(i[0][0]+i[1][0]+i[2][0])
        v.append(i[0][1]+i[1][1]+i[2][1])
    for j in range(sum,0,-1):
        for k in range(len(p)):
            if j>=p[k] :
                dp[j]=max(dp[j],v[k]+dp[j-p[k]])//得到价值=》最大满意度数组
print(dp[sum]*base)//返回给定价值所对应的满意度