题解 | #购物单#

研究了很久,详细代码如下,每一步都有注释,欢迎讨论

N, m = map(int, input().split())
# 价格除10 减少循环次数
N //= 10
# 定义价格 和重要度数组[0,0,0] 代表主件 附件1 附件2
# 价格数组 要循环到m+1 个 多一个防止后面物品重1开始循环 超出列表
V = [[0, 0, 0] for _ in range(m + 1)]
# 重要度数组
P = [[0, 0, 0] for _ in range(m + 1)]
# 价格和重要度 二维数组
dp = [[0] * (N + 1) for _ in range(m + 1)]

# 开始处理 单价 和满意度数组
for i in range(1, m + 1):
    # 把价格 重要度 主件标志取出来 v p q
    v, p, q = map(int, input().split())
    # 价格也除10
    v //= 10
    if q == 0:
        # 是主件 把单价和满意度放在列表下标为1的 下标0的 第一个数据废弃不用 这里有个小bug并不知道 哪个附件对应哪个主件 所以做法
        # 做法是 先给主件匹配附件 匹配完了就不用了

        V[i][0] = v
        P[i][0] = v * p
    elif V[q][1] == 0:
        # 如果不是主件 就找附件,但因为不止一个附件 所以不能else  先找第一个 再找第二个就完了
        V[q][1] = v
        P[q][1] = v * p
    else:
        V[q][2] = v
        P[q][2] = v * p
# print(V)
# print(P)
# 单价和 满意度的数组就完成了


# 先遍历物品数量
for i in range(1, m + 1): # i 代表第i个物品
    # 遍历金钱 从当前金钱到0 逐渐减少
    for j in range(N, -1, -1):  # j代表剩余的钱
        # 如果当前金钱可以支付起主件
        if j >= V[i][0]:  # V[i][0]代表第i个物品的主件价格
            # 要么购买主件的满意度 和不购买的满意度 取最大值 dp[i - 1][j] 代表 购买前i个物品的满意度
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - V[i][0]] + P[i][0])
            # 可以购买主件 + 附件1
            if j >= (V[i][0] + V[i][1]):
                # 不购买主件 购买 主件  购买主件+附件1
                dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i - 1][j - V[i][0]] + P[i][0],
                               dp[i - 1][j - V[i][0] - V[i][1]] + P[i][0] + P[i][1])
            # 可以购买主件 + 附件2
            if j >= (V[i][0] + V[i][2]):
                # 不购买主件 购买 主件  购买主件+附件2
                dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i - 1][j - V[i][0]] + P[i][0],
                               dp[i - 1][j - V[i][0] - V[i][2]] + P[i][0] + P[i][2])
                # 可以购买主件 + 附件1 + 附件2
                if j >= (V[i][0] + V[i][1] + V[i][2]):
                    # 不购买主件 购买 主件  购买主件+附件1 +附件2
                    dp[i][j] = max(dp[i][j], dp[i - 1][j],
                                   dp[i - 1][j - V[i][0] - V[i][1] - V[i][2]] + P[i][0] + P[i][1] + P[i][2])
        else:
            # 购买不了主件 只能后面前 i-1商品了
            dp[i][j] = dp[i - 1][j]
print(dp[-1][-1] * 10)