编程到底难在哪里？
来源：牛客-华为机考-HJ28素数伴侣
点击上方"互联网求职达人"，选择"设为置顶or星标"
第一时间获取最实用的求职以及备考信息
✦
HJ28素数伴侣
题目描述：
王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的。如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。满意度是指所购买的每件物品的价格与重要度的乘积的总和。
输入描述：
输入的第 1 行，为两个正整数N，m，用一个空格隔开：（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。） 从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q （其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
输出描述：
输出一个正整数，为张强可以获得的最大的满意度。
示例：
输入：
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0
输出： 2200
答案：
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()
解题思路：
动态规划，先处理物品之间的关系，将附件与主件建立联系，然后用0-1背包的方法计算最大满意度。
这道题目是一个带有条件约束的背包问题。我们首先需要将主件和附件区分开来，并将它们的价格和重要度按要求计算。接下来，我们将使用动态规划解决这个问题。
将输入的物品数据分成两个部分：主件和附件。主件是附件所依赖的物品，附件是与主件相关的物品。我们用一个主件列表存储所有主件的价格、重要度乘积和索引。同时，我们使用一个二维列表存储每个主件的附件。
初始化一个长度为 N//10+1 的动态规划数组 dp，其中 N 为总钱数。这里我们将所有物品的价格除以 10，以简化计算。数组 dp 用于存储在不同预算下所能获得的最大满意度。
遍历所有主件，对于每一个主件，我们需要分别考虑以下情况：
只购买主件，不购买附件。更新 dp 数组，将当前预算下的满意度与购买主件后的满意度进行比较，取较大值。
购买主件和一个附件。遍历每一个附件，更新 dp 数组，将当前预算下的满意度与购买主件及附件后的满意度进行比较，取较大值。
购买主件和两个附件。遍历所有附件组合，更新 dp 数组，将当前预算下的满意度与购买主件及两个附件后的满意度进行比较，取较大值。
最后，dp 数组的最后一个元素就是我们要求的最大满意度。
通过这个思路，我们可以解决这个带有条件约束的背包问题。
对于正在准备机考的小伙伴，以下是一些建议：
扎实的编程基础：熟练掌握至少一种编程语言，掌握基本的语法和编程规范。同时，要熟悉常用的数据结构和算法。
练习经典题目：在LeetCode、牛客网等在线编程平台上练习经典的编程题目，提高解题速度和准确率。
熟悉输入输出格式：熟悉不同编程题目的输入输出格式，尤其是一些特定的输入输出要求，如ACM模式等。
提高调试能力：在解题过程中，遇到问题要学会独立调试，掌握使用调试工具的方法，提高代码质量。
时间管理：在机考过程中，合理分配时间，先解决自己擅长的题目，提高通过率。
学习解题技巧：多参考一些编程书籍和教程，学习不同类型题目的解题技巧和方法，提高解题能力。
复习计算机基础知识：复习计算机基础知识，如操作系统、计算机网络、数据库等，这些知识在机考中也可能会涉及。
模拟考试：在准备过程中，进行模拟考试，模拟真实的考试环境，提高自己的适应能力。
保持良好的心态：在面对机考时，保持良好的心态，遇到困难不要慌张，冷静分析，相信自己的实力。
及时总结和反思：在练习和考试过程中，要及时总结自己的不足和错误，进行反思和改进，不断提高自己的能力。
