题解 | #购物单#

购物单

https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

需要优化此段代码

import sys

j=''

primary,annex = {},{}

n,m=0,0

for line in sys.stdin:

a = line.split()

if len(a) == 2:

n,m=map(int,a)

if len(a) == 3:

x,y,z = map(int,a)

if z==0:

primary[len(j)] = [x,y]

else:

if z in annex:

annex[z].append([x,y])

else:

annex[z]=[[x,y]]

j+=f'{1}'

dp = [0]*(n-1)

for i in primary:

w_temp,v_temp = [],[] #【物品1，物品1+附件1】【满意度1，满意度2】

w_temp.append(primary[i][0]) #主件i的价格

v_temp.append(primary[i][0]*primary[i][1]) #主件i的满意度

if i in annex: #如果存在附件

w_temp.append(w_temp[0]+annex[i][0][0]) #i【物品1+附件1的价格】

v_temp.append(v_temp[0]+annex[i][0][0]*annex[i][0][1]) # [满意度2]

if len(annex[i])>1:

w_temp.append(w_temp[0]+annex[i][1][0]) #i【物品1+附件2的价格】

v_temp.append(v_temp[0]+annex[i][1][0]*annex[i][1][1]) #[满意度3]

w_temp.append(w_temp[0]+annex[i][0][0]+annex[i][1][0]) #【物品1+附件1+附件2的价格】

v_temp.append(v_temp[0]+annex[i][0][0]*annex[i][0][1]+annex[i][0][0]+annex[i][1][0])

for j in range(n,n-1,10):

for k in range(len(w_temp)):

if j-w_temp[i]>=0:

dp[j] = max(dp[j], dp[j-w_temp[i]+v_temp[i]])

print(dp[n])

数据输出解析

n, m = map(int, input().split())
primary, annex = {}, {}
for i in range(1, m + 1):
    x, y, z = map(int, input().split())
    if z == 0:
        primary[i] = [x, y]
    else:
        if z in annex:
            annex[z].append([x, y])
        else:
            annex[z] = [[x, y]]
dp = [0] * (n + 1)

for key in primary:
    w, v = [], []
    w.append(primary[key][0])  # 1、主件
    v.append(primary[key][0] * primary[key][1])
    if key in annex:  # 存在附件
        w.append(w[0] + annex[key][0][0])  # 2、主件+附件1
        v.append(v[0] + annex[key][0][0] * annex[key][0][1])
        if len(annex[key]) > 1:  # 附件个数为2
            w.append(w[0] + annex[key][1][0])  # 3、主件+附件2
            v.append(v[0] + annex[key][1][0] * annex[key][1][1])
            w.append(w[0] + annex[key][0][0] + annex[key][1][0])  # 4、主件+附件1+附件2
            v.append(v[0] + annex[key][0][0] * annex[key][0][1] + annex[key][1][0] * annex[key][1][1])
    print(w,v)
    for j in range(n, -1, -10):  # 物品的价格是10的整数倍
        for k in range(len(w)):
            if j - w[k] >= 0:
                print(f'    花{j}元 - 主件物品价格{w[k]} = 还剩下{j - w[k]}元   比较第 {j}个格子{dp[j]}元 和第 {j - w[k]} 个格子（{dp[j - w[k]]}+主件和附物品价值{v[k]}）={dp[j - w[k]] + v[k]}元，取最大值{max(dp[j], dp[j - w[k]] + v[k])} '
                      f'第{j}个格子放入价值{max(dp[j], dp[j - w[k]] + v[k])}的物品')
                dp[j] = max(dp[j], dp[j - w[k]] + v[k])

==================== 代码解析 =================

数据：

50 5 20 3 5 20 3 5 10 3 0 10 2 0 10 1 0

图示假设：有一个背包，背包内有5个位------>红色代表价格：当物品的价格为10元时,占用一个位置(标红)。价格为30，占用三个位置

------->数字代表价值：右侧红色方框数字代表当前物品满意度

左侧第一竖排代表：满意度最高的物品

其余竖排代表：满意度累加

代码 dp[j - w[k]] 的解释： ”其余位置“ D-A

代码 dp[j - w[k]] + v[k] 的解释：在 ”其余位置“ ，累加满意度

代码 max(dp[j], dp[j - w[k]] + v[k]) 的解释：比较在位置j当前物品满意度与 ”其余位置“的满意度，取最大值

第二张图代表物品2 当 j 位于B/C/D竖时，满意度 50=30+当前物品满意度当前30<50

当j位于A竖时，当前(物品2) 20 < (物品1满意度)30