华为笔试机考丨牛客每天一道·三道编程题O题解 | #购物单#

def main():
    N, m = map(int, input().split())
    N = N // 10
    items = [tuple(map(int, input().split())) for _ in range(m)]

    primary, accessory = [], [[] for _ in range(m)]
    for i, item in enumerate(items):
        if item[2] == 0:
            primary.append((item[0] // 10, item[1] * item[0], i))
        else:
            accessory[item[2] - 1].append((item[0] // 10, item[1] * item[0]))

    dp = [0] * (N + 1)
    for item in primary:
        for i in range(N, item[0] - 1, -1):
            dp[i] = max(dp[i], dp[i - item[0]] + item[1])
            for acc in accessory[item[2]]:
                if i >= item[0] + acc[0]:
                    dp[i] = max(dp[i], dp[i - item[0] - acc[0]] + item[1] + acc[1])
                if len(accessory[item[2]]) > 1:
                    acc2 = accessory[item[2]][0] if accessory[item[2]][1] == acc else accessory[item[2]][1]
                    if i >= item[0] + acc[0] + acc2[0]:
                        dp[i] = max(dp[i], dp[i - item[0] - acc[0] - acc2[0]] + item[1] + acc[1] + acc2[1])

    print(dp[-1])


if __name__ == "__main__":
    main()

这道题目是一个带有条件约束的背包问题。我们首先需要将主件和附件区分开来，并将它们的价格和重要度按要求计算。接下来，我们将使用动态规划解决这个问题。

1. 将输入的物品数据分成两个部分：主件和附件。主件是附件所依赖的物品，附件是与主件相关的物品。我们用一个主件列表存储所有主件的价格、重要度乘积和索引。同时，我们使用一个二维列表存储每个主件的附件。
2. 初始化一个长度为 N//10+1 的动态规划数组 dp，其中 N 为总钱数。这里我们将所有物品的价格除以 10，以简化计算。数组 dp 用于存储在不同预算下所能获得的最大满意度。
3. 遍历所有主件，对于每一个主件，我们需要分别考虑以下情况：只购买主件，不购买附件。更新 dp 数组，将当前预算下的满意度与购买主件后的满意度进行比较，取较大值。购买主件和一个附件。遍历每一个附件，更新 dp 数组，将当前预算下的满意度与购买主件及附件后的满意度进行比较，取较大值。购买主件和两个附件。遍历所有附件组合，更新 dp 数组，将当前预算下的满意度与购买主件及两个附件后的满意度进行比较，取较大值。
4. 最后，dp 数组的最后一个元素就是我们要求的最大满意度。

通过这个思路，我们可以解决这个带有条件约束的背包问题。