题解 | #购物单# （转载）
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
#来自https://blog.nowcoder.net/n/bf369610fdec431fb0c02e09557004af?f=comment的解答，非常精彩，手敲一遍仅仅练习记录用
while True:
try:
# 总金额， 物品数量
total, k = list(map(int, input().split(" ")))
W = {}
V = {}
total = int(total / 10)
main_key = []
for i in range(1, k + 1):
W[i] = [0, 0, 0]
V[i] = [0, 0, 0]
for i in range(k):
# 单价，权重， 类别（主/辅）
v, p, q = list(map(int, input().split(" ")))
if q == 0:
W[i + 1][0] = int(v / 10)
V[i + 1][0] = int(v * p / 10)
main_key.append(i + 1)
else:
if W[q][1] == 0:
W[q][1] = int(v / 10)
V[q][1] = int(v * p / 10)
else:
W[q][2] = int(v / 10)
V[q][2] = int(v * p / 10)
W_lst = []
V_lst = []
for key in W.keys():
if key in main_key:
W_lst.append(W[key])
V_lst.append(V[key])
m = len(W_lst) # 主件数
dp = [[0] * (total + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
w1 = W_lst[i - 1][0]
w2 = W_lst[i - 1][1]
w3 = W_lst[i - 1][2]
v1 = V_lst[i - 1][0]
v2 = V_lst[i - 1][1]
v3 = V_lst[i - 1][2]
for j in range(total + 1):
dp[i][j] = dp[i - 1][j] # 不放
if j - w1 >= 0: # 放1个主件
dp[i][j] = max(dp[i][j], dp[i - 1][j - w1] + v1)
if j - w1 - w2 >= 0: # 放1主件+附件1
dp[i][j] = max(dp[i][j], dp[i - 1][j - w1 - w2] + v1 + v2)
if j - w1 - w3 >= 0: # 放1主件+附件2
dp[i][j] = max(dp[i][j], dp[i - 1][j - w1 - w3] + v1 + v3)
if j - w1 - w2 - w3 >= 0: # 放1主件+附件1+附件2
dp[i][j] = max(dp[i][j], dp[i - 1][j - w1 - w2 - w3] + v1 + v2 + v3)
print(int(dp[m][total] * 10))
except:
break
