题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
研究了很久,详细代码如下,每一步都有注释,欢迎讨论
N, m = map(int, input().split()) # 价格除10 减少循环次数 N //= 10 # 定义价格 和重要度数组[0,0,0] 代表主件 附件1 附件2 # 价格数组 要循环到m+1 个 多一个防止后面物品重1开始循环 超出列表 V = [[0, 0, 0] for _ in range(m + 1)] # 重要度数组 P = [[0, 0, 0] for _ in range(m + 1)] # 价格和重要度 二维数组 dp = [[0] * (N + 1) for _ in range(m + 1)] # 开始处理 单价 和满意度数组 for i in range(1, m + 1): # 把价格 重要度 主件标志取出来 v p q v, p, q = map(int, input().split()) # 价格也除10 v //= 10 if q == 0: # 是主件 把单价和满意度放在列表下标为1的 下标0的 第一个数据废弃不用 这里有个小bug并不知道 哪个附件对应哪个主件 所以做法 # 做法是 先给主件匹配附件 匹配完了就不用了 V[i][0] = v P[i][0] = v * p elif V[q][1] == 0: # 如果不是主件 就找附件,但因为不止一个附件 所以不能else 先找第一个 再找第二个就完了 V[q][1] = v P[q][1] = v * p else: V[q][2] = v P[q][2] = v * p # print(V) # print(P) # 单价和 满意度的数组就完成了 # 先遍历物品数量 for i in range(1, m + 1): # i 代表第i个物品 # 遍历金钱 从当前金钱到0 逐渐减少 for j in range(N, -1, -1): # j代表剩余的钱 # 如果当前金钱可以支付起主件 if j >= V[i][0]: # V[i][0]代表第i个物品的主件价格 # 要么购买主件的满意度 和不购买的满意度 取最大值 dp[i - 1][j] 代表 购买前i个物品的满意度 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - V[i][0]] + P[i][0]) # 可以购买主件 + 附件1 if j >= (V[i][0] + V[i][1]): # 不购买主件 购买 主件 购买主件+附件1 dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i - 1][j - V[i][0]] + P[i][0], dp[i - 1][j - V[i][0] - V[i][1]] + P[i][0] + P[i][1]) # 可以购买主件 + 附件2 if j >= (V[i][0] + V[i][2]): # 不购买主件 购买 主件 购买主件+附件2 dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i - 1][j - V[i][0]] + P[i][0], dp[i - 1][j - V[i][0] - V[i][2]] + P[i][0] + P[i][2]) # 可以购买主件 + 附件1 + 附件2 if j >= (V[i][0] + V[i][1] + V[i][2]): # 不购买主件 购买 主件 购买主件+附件1 +附件2 dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i - 1][j - V[i][0] - V[i][1] - V[i][2]] + P[i][0] + P[i][1] + P[i][2]) else: # 购买不了主件 只能后面前 i-1商品了 dp[i][j] = dp[i - 1][j] print(dp[-1][-1] * 10)
