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

购物单

https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

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 数组的最后一个元素就是我们要求的最大满意度。

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

#23届找工作求助阵地##题库##编程题#
全部评论

相关推荐

点赞 评论 收藏
分享
2024-11-14 16:09
门头沟学院 Java
Java抽象带篮子:可以看看我的苍穹外卖话术帖子和八股笔记帖子
点赞 评论 收藏
分享
2024-11-26 15:41
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务