题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
from ctypes import Array
import sys
while True:
try:
#总价格，商品数量
total, k = list(map(int, input().split()))
#主商品
main_key = []
#权重满意度
perPrice = {}
#商品价格
perValue = {}
#主商品数据
mainPrice = []
mainValue = []
for i in range(1, k + 1):
perPrice[i] = [0, 0, 0]
perValue[i] = [0, 0, 0]
for i in range(1, k + 1):
v, p, q = list(map(int, input().split()))
vp = int(v*p/10)
if q == 0:
perPrice[i][0] = vp
perValue[i][0] = int(v / 10)
main_key.append(i)
else:
if perPrice[q][1] == 0:
perPrice[q][1] = vp
perValue[q][1] = int(v / 10)
else:
perPrice[q][2] = vp
perValue[q][2] = int(v / 10)
# for key in main_key:
for key in perPrice.keys():
if key in main_key:
mainPrice.append(perPrice[key])
mainValue.append(perValue[key])
mm = len(mainPrice)
nn = int(total / 10)
dp = [[0] * (nn + 1) for _ in range(mm + 1)]
for i in range(1, mm + 1):
p1, p2, p3 = (
mainPrice[i - 1][0],
mainPrice[i - 1][1],
mainPrice[i - 1][2],
)
v1, v2, v3 = (
mainValue[i - 1][0],
mainValue[i - 1][1],
mainValue[i - 1][2],
)
for j in range(nn + 1):
dp[i][j] = dp[i - 1][j]
if j - v1 >= 0:
dp[i][j] = max(dp[i][j], p1 + dp[i - 1][j - v1])
if j - v1 - v2 >= 0:
dp[i][j] = max(dp[i][j], p1 + p2 + dp[i - 1][j - v1 - v2])
if j - v1 - v3 >= 0:
dp[i][j] = max(dp[i][j], p1 + p3 + dp[i - 1][j - v1 - v3])
if j - v1 - v2 - v3 >= 0:
dp[i][j] = max(
dp[i][j], p1 + p2 + p3 + dp[i - 1][j - v1 - v2 - v3]
)
xx = dp[mm][nn]
print(dp[mm][nn]*10)
except:
break
