题解 | 购物单

c, n = map(int, input().split())

m_goods = []
a_goods = []
for i in range(n):
    cost, importance, follow = map(int, input().split())
    if follow == 0:  # 主件
        m_goods.append([cost, cost * importance, follow, i + 1])
    else:  # 附件
        a_goods.append([cost, cost * importance, follow])

# print(m_goods)
# print(a_goods)
# [[10, 30, 0, 3], [10, 20, 0, 4], [10, 10, 0, 5]]
# [[20, 60, 5], [20, 60, 5]]

goods = [[] for _ in range(len(m_goods))]
for i in range(len(m_goods)):
    goods[i].append(m_goods[i])
for i in range(len(a_goods)):
    for j in range(len(m_goods)):
        if a_goods[i][2] == m_goods[j][3]:  # 找到附件的主件
            goods[j].append(a_goods[i])

# for good in goods:
#     print(good)
# [[10, 30, 0, 3]]
# [[10, 20, 0, 4]]
# [[10, 10, 0, 5], [20, 60], [20, 60]]

for i in range (len(goods)):
    goods[i][0].pop(2)
    for j in range(1,len(goods[i])):
        goods[i][j].pop(2)
    goods[i][0].pop(2)#去掉没用的数据：所属主件、物品编号


# for good in goods:
#     print(good)

for i in range (len(goods)):
    if len(goods[i])==2:
        goods[i][1]=[x+y for x,y in zip(goods[i][0],goods[i][1])]
    if len(goods[i])==3:
        goods[i].append([0,0])
        goods[i][3]=[x+y for x,y in zip(goods[i][1],goods[i][2])]
        for j in range(1,4):
            goods[i][j][0]+=goods[i][0][0]
            goods[i][j][1]+=goods[i][0][1]

# for good in goods:
#     print(good)

dp=[0 for _ in range(c+1)]
for good in goods:
    for i in range(c,-1,-1):
        for weight,value in good:
            if weight<=i and value + dp[i-weight]>dp[i]:
                dp[i]=value + dp[i-weight]

print(max(dp))