题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
import sys # 典型的 01 背包问题，只取一次。
N,m = input().split()
N,m = int(N)//10,int(m)
values,utility = [[0 for _ in range(3)] for s in range(0,m+1)],\
[[0 for _ in range(3)] for s in range(0,m+1)]
i = 1
for line in sys.stdin:
a = line.split()
v,p,q = int(a[0])//10,int(a[1]),int(a[2])
# print(v,p,q)
if q != 0: # 附件是 跟在 主键后面。 这个存储结构 模仿的描述图片。可以清晰看见主附件结构。
if values[q][1]==0: # 附件 1
values[q][1] = v
utility[q][1] = p*v
else: # 附件 2
values[q][2] = v
utility[q][2] = p*v
else: # 主件
values[i][0] = v
utility[i][0] = p*v
i += 1
# python 一用 insert 就会超时！！！注意！
# values.insert(0,[0,0,0]) # 考虑到后面都是 假定从 1开始取的，物品也是从1开始标号
# utility.insert(0,[0,0,0]) # 目的是方便后面的 递推公式 i-1 。
# print(values)
# print(utility)
# d[i][j] 定义为 背包为j容量 ，0-i 产品中任选一个，的效用。
# 初始化
d = [ [ 0 for b in range(32001) ] for a in range(61)]
# for _ in range(int(m)):
# d[_][0] = 0
# for __ in range(int(m)):
# for _ in range(int(N)):
# if values[__][0] != 0:
# if _ < values[__][0]:
# d[__][_] = 0
# else:
# d[__][_] = utility[__][0]
# # print(d)
result = 0
for i in range(1,m+1): # 物件
for j in range(1,N+1): # 背包
# 没有满足任何件,取不到 i ;
d[i][j] = d[i-1][j]
if j >= values[i][0]: # 仅仅满足主件
d[i][j] = max(d[i][j],d[i-1][j-values[i][0]] + utility[i][0] )
if j >= values[i][0]+values[i][1]: # 满足主件 + 第 1 个附件 这里不取的时候，是 d[i][j]，d[i][j] 指的是 上一个if 的结果，像冒泡一样层层递进。
d[i][j] = max(d[i][j],d[i-1][j-values[i][0]-values[i][1]] + utility[i][0]+utility[i][1])
if j >= values[i][0]+values[i][2]: # 满足主件 + 第 2 个附件
d[i][j] = max(d[i][j],d[i-1][j-values[i][0]-values[i][2]] + utility[i][0]+utility[i][2])
if j >= values[i][0]+values[i][1]+values[i][2]: # 满足主件 + 第 1 和 第 2 个附件
d[i][j] = max(d[i][j],d[i-1][j-values[i][0]-values[i][1]-values[i][2]] + utility[i][0]+utility[i][1]+utility[i][2] )
# print('ok this is ',d[i][j])
# result = d[i][j]
# 从 5 种情况中找出最大 的 utility 效用。每种情况下 又分 取到这样的i 和没取到这样的 i 两种情况，取他们的最大值，注意 取不到的情况 就是退回到 上一个 if 语句下的 d[i][j] 了，因为他们是环环相扣的，目的就是找出 5种情况下的最大值。
print(d[i][j]*10)
投递中国国际金融股份有限公司等公司10个岗位 >
查看16道真题和解析
