题解 | 购物单

def main():
    import sys

    input = sys.stdin.read
    data = input().split()

    n = int(data[0])  # 预算
    m = int(data[1])  # 物品总数

    # 价格、重要度、满意度（价格*重要度）、主附件关系
    prices = [0] * (m + 1)
    importance = [0] * (m + 1)
    satisfaction = [0] * (m + 1)
    main_to_attachments = [[] for _ in range(m + 1)]
    is_main = [False] * (m + 1)

    idx = 2
    for i in range(1, m + 1):
        v = int(data[idx])
        idx += 1
        w = int(data[idx])
        idx += 1
        q = int(data[idx])
        idx += 1
        prices[i] = v
        importance[i] = w
        satisfaction[i] = v * w

        if q == 0:
            is_main[i] = True
        else:
            main_to_attachments[q].append(i)

    main_items = []
    for i in range(1, m + 1):
        if is_main[i]:
            main_items.append(i)

    # 分组背包 DP
    dp = [0] * (n + 1)

    for main_item in main_items:  # 这里应该是 main_item，不是 main_id
        # 生成该主件所有可能的购买组合
        combos = []
        # 只买主件
        combos.append((prices[main_item], satisfaction[main_item]))

        attachments = main_to_attachments[main_item]
        att_count = len(attachments)

        # 枚举附件的所有购买子集
        if att_count >= 1:
            a1 = attachments[0]
            combos.append(
                (
                    prices[main_item] + prices[a1],
                    satisfaction[main_item] + satisfaction[a1],
                )
            )
        if att_count >= 2:
            a2 = attachments[1]
            combos.append(
                (
                    prices[main_item] + prices[a2],
                    satisfaction[main_item] + satisfaction[a2],
                )
            )
            combos.append(
                (
                    prices[main_item] + prices[a1] + prices[a2],
                    satisfaction[main_item] + satisfaction[a1] + satisfaction[a2],
                )
            )

        # 分组背包更新
        new_dp = dp[:] 

        for budget in range(n, -1, -1):
            for v_sum, s_sum in combos:
                if v_sum <= budget:
                    new_dp[budget] = max(new_dp[budget], dp[budget - v_sum] + s_sum)
        dp = new_dp

    print(dp[n])


if __name__ == "__main__":
    main()


# awsl.....组合部分吗给我整了半天才理顺，计算机学得好的人一定都是天才