题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
n, m = map(int, input().split()) primary, annex = {}, {} # 分别存放主件和附件的{key: [weight, value]} for i in range(1, m + 1): x, y, z = map(int, input().split()) if z == 0: # 主件 primary[i] = [x, y] else: # 附件 if z in annex: # 第二个附件 annex[z].append([x, y]) else: # 第一个附件 annex[z] = [[x, y]] m = len(primary) # 主件个数为物品个数 # 算出每个主件所有方案的weight和value,w[i][j], v[i][j] w, v = [[]], [[]] for key in primary: w_temp, v_temp = [], [] w_temp.append(primary[key][0]) # 主件: j=0 v_temp.append(primary[key][0] * primary[key][1]) if key in annex: w_temp.append(w_temp[0] + annex[key][0][0]) # 主件+附件1: j=1 v_temp.append(v_temp[0] + annex[key][0][0] * annex[key][0][1]) if len(annex[key]) == 2: w_temp.append(w_temp[0] + annex[key][1][0]) # 主件+附件2: j=2 v_temp.append(v_temp[0] + annex[key][1][0] * annex[key][1][1]) w_temp.append(w_temp[0] + annex[key][0][0] + annex[key][1][0]) # 主件+附件1+附件2: j=3 v_temp.append( v_temp[0] + annex[key][0][0] * annex[key][0][1] + annex[key][1][0] * annex[key][1][1] ) w.append(w_temp) v.append(v_temp) # print(w) # print(v) # dp[i][j]表示前i个物品,背包重量为j的情况下能装的最大价值 dp = [[0]*(n+1) for _ in range(m+1)] #定义状态转移数组 for i in range(1, m+1): for j in range(10, n+1, 10): max_i = dp[i-1][j] for k in range(len(w[i])): #遍历当前商品的4种情况,主件,主件+附件1,主件+附件2,主件+附件1+附件2 if j - w[i][k] >= 0: #判断背包重量是否足够 max_i = max(max_i, dp[i-1][j-w[i][k]]+v[i][k]) dp[i][j] = max_i print(dp[m][n])