题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
不是背包问题,把他变成背包问题
N, m = list(map(int, input().split())) main = dict() appendage = dict() for i in range(1, m+1): v, p, q = list(map(int,input().split())) if q == 0: main[i] = [v, v*p] elif q in appendage: appendage[q].append([v, v*p]) else: appendage[q] = [[v, v*p]] dp = [0] * (N+1) for key, value in main.items(): w = [] v = [] w.append(value[0]) v.append(value[1]) if key in appendage: w.append(w[0] + appendage[key][0][0]) v.append(v[0] + appendage[key][0][1]) if len(appendage[key]) == 2: w.append(w[0]+appendage[key][1][0]) v.append(v[0]+appendage[key][1][1]) w.append(w[0]+appendage[key][0][0]+appendage[key][1][0]) v.append(v[0]+appendage[key][0][1]+appendage[key][1][1]) for i in range(N, -1, -10): for k in range(len(w)): if i >= w[k]: dp[i] = max(dp[i], dp[i-w[k]] + v[k]) print(dp[N])