题目描述： 王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件附件电脑打印机，扫描仪书柜图书书桌台灯，文具工作椅无如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
请你帮助王强设计一个满足要求的购物单。
输入描述：
输入的第 1 行，为两个正整数，用一个空格隔开：N m （其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。） 从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q （其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
输出描述：
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。
示例1： 输入：
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0
输出：
2200
题目分析： 首先，附件必须在买了主件之后才能购买，为了降低题目的复杂度，可以把附件都合并到主件中，与主件一同判断。 其次，题目是希望取得分数的最高值，那么购买当前主件所获得的最高分，就等于 还没买当前主件时获得的最高分 加上 当前主件的分值。 （上一句可能有些绕，例如目前已经花了100元，当前主件是20元，重要度是2，那么主件的分值就是40。那么买这个主件之前是花了80元，如果花了80元时获得的最高分加上40就是花了100元时的最高分，那么就更新100元时的最高分。）
按照这个逻辑，我们要求的就是已经花了N元时的最高分，再一步步往回推花了比N元少的时候的最高分。 所以解决方案中我们会设定一个列表 f ，f[i] 代表花了 i 元时的最高分（0 <= i <= N），这个列表用于实现动态规划。
定好了动态规划的大致方向后，其实购买主件是有五种情况的：不买主件、只买主件、主附1、主附2、主附12。 同样的，也是判断在花了当前 f[i] 这么多钱后，哪种情况的分数最高，即代码中的 max_，最终再填回 f[i] 。
大致思路如上了，后面的细节再通过代码注释解释：
class Good(object): def __init__(self, v, vp): self.v = v # 价格 self.vp = vp # 价格 * 重要度 # 便于调试 def __str__(self): return "{} {}".format(self.v, self.vp) def __repr__(self): return self.__str__() if __name__ == "__main__": tmp = input() N, m = tmp.split() # 商品价格都是10的倍数，因此个位数的总钱数是没用的 # 对总钱数和商品价格都除以10，可以加速 N, m = int(N) // 10, int(m) # goods[0]是不用的，只用goods[1] ~ goods[m] # 因为题目给的 q 也是从 1 开始 goods = [[None for _ in range(3)] for _ in range(m + 1)] for i in range(1, m + 1): # 注意要从1到m v, p, q = input().split() v, p, q = int(v) // 10, int(p), int(q) tmp = Good(v, v * p) # 0 放主件，1 和 2 分别放两个附件 if q == 0: goods[i][0] = tmp elif goods[q][1] is None: goods[q][1] = tmp else: goods[q][2] = tmp f = [0 for _ in range(N + 1)] # f[j]代表花了j元时最高的分数 for i in range(1, m + 1): if goods[i][0] is None: continue # 如果是附件，就跳过 for j in range(N, -1, -1): # 从N到0 # N要倒叙遍历是因为f[j]要基于比j少钱的结果来计算 # 而同一个商品不能买两次 # 所以倒叙能避免重复买的问题 # 举个正序的反例： # 例如目前循环到商品3，价格是20 # 在j=20时，足够钱买商品3 # 遍历到j=40时，依然足够钱买商品3，就会重复购买 # 假如是倒叙，他们所比较的情况都是这个商品还没买过的情况 # 所以倒叙才是OK的 master = goods[i][0] max_ = f[j] # 如果够钱，且买这master之前的最大值（f[j - master.v]）加上当前master的价值 # 比现在的总价值高，则更新总价值max_ if j >= master.v and max_ < f[j - master.v] + master.vp: max_ = f[j - master.v] + master.vp if goods[i][1] is not None: # 如果有附件1 vt = master.v + goods[i][1].v # 主件和附件1的总价，t=total vpt = master.vp + goods[i][1].vp # 总价值 # 同样的，如果比之前大，就更新总价值 if j >= vt and max_ < f[j - vt] + vpt: max_ = f[j - vt] + vpt # 如果有附件2，有两种情况 # 主件加附件2 # 主件加附件1加附件2 if goods[i][2] is not None: vt = master.v + goods[i][2].v vpt = master.vp + goods[i][2].vp if j >= vt and max_ < f[j - vt] + vpt: max_ = f[j - vt] + vpt vt = master.v + goods[i][1].v + goods[i][2].v vpt = master.vp + goods[i][1].vp + goods[i][2].vp if j >= vt and max_ < f[j - vt] + vpt: max_ = f[j - vt] + vpt f[j] = max_ # 最终max_就会是五种情况中的最大值 print(f[N] * 10)至此结束了，欢迎留言沟通~
参考来源： 讨论区的高赞java实现：
