题解 | #购物单#

n, m = map(int, input().split())
primary, annex = {}, {}  # 分别存放主件和附件的{key: [weight, value]}
for i in range(1, m + 1):
    x, y, z = map(int, input().split())
    if z == 0:  # 主件
        primary[i] = [x, y]
    else:  # 附件
        if z in annex:  # 第二个附件
            annex[z].append([x, y])
        else:  # 第一个附件
            annex[z] = [[x, y]]

m = len(primary)  # 主件个数为物品个数
# 算出每个主件所有方案的weight和value，w[i][j], v[i][j]
w, v = [[]], [[]]
for key in primary:
    w_temp, v_temp = [], []
    w_temp.append(primary[key][0])  # 主件: j=0
    v_temp.append(primary[key][0] * primary[key][1])
    if key in annex:
        w_temp.append(w_temp[0] + annex[key][0][0])  # 主件+附件1: j=1
        v_temp.append(v_temp[0] + annex[key][0][0] * annex[key][0][1])
        if len(annex[key]) == 2:
            w_temp.append(w_temp[0] + annex[key][1][0])  # 主件+附件2: j=2
            v_temp.append(v_temp[0] + annex[key][1][0] * annex[key][1][1])

            w_temp.append(w_temp[0] + annex[key][0][0] + annex[key][1][0])  # 主件+附件1+附件2: j=3
            v_temp.append(
                v_temp[0]
                + annex[key][0][0] * annex[key][0][1]
                + annex[key][1][0] * annex[key][1][1]
            )

    w.append(w_temp)
    v.append(v_temp)
# print(w)
# print(v)
# dp[i][j]表示前i个物品，背包重量为j的情况下能装的最大价值
dp = [[0]*(n+1) for _ in range(m+1)] #定义状态转移数组
for i in range(1, m+1):
    for j in range(10, n+1, 10):
        max_i = dp[i-1][j]
        for k in range(len(w[i])): #遍历当前商品的4种情况，主件，主件+附件1，主件+附件2，主件+附件1+附件2
            if j - w[i][k] >= 0: #判断背包重量是否足够
                max_i = max(max_i, dp[i-1][j-w[i][k]]+v[i][k])
        dp[i][j] = max_i
print(dp[m][n])