HJ16 题解 | #购物单#

这道题是01背包的衍生题目

我们由浅入深分析一下

如果没有附件，那么就是一道典型的01背包题目，只是dp[i][j]的定义和递推公式含义有点不一样。

先回顾一下01背包的dp定义：

• dp[i][j]表示选择前i个物品，背包容量为j的情况下能装的最大价值

而此题dp定义为：

• dp[i][j]表示选择前i个物品，金额为j的情况下能买到的最大满意度

01背包递推公式为：

• dp[i][j]=max(dp[i-1][j],dp[i-1][j-vi]+wi) 其中vi为物品i的体积，wi为物品i的价值

而此题的递推公式为：

• dp[i][j]=max(dp[i-1][j],dp[i-1][j-vi]+wi) 其中vi为物品i的体积，wi为物品i的满意度
• wi=vi * pi 其中pi为物品i的重要度

这样就得到了此题没有附件的情况的解法

现在分析有附件的情况

由于附件不能单独出现，所以针对主件i以及他的附件有可能的情况有这几种：

• 不装主件i
• 装主件i
• 装主件i+附件1
• 装主件i+附件2
• 装主件i+附件1+附件2

那么我们只需要在上面没有附件的基础上加上一个枚举——在分析到主件i的时候枚举上面这5种情况即可，然后dp[i][j]取其中的最大值。

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append([int(j) for j in input().split()])
if m==1:#特判只有一个物品，事实证明这道题测试数据没有需要特判的
    if a[0][0]<=n:#买得起
        print(a[0][0]*a[0][1])
        exit()
zhu=[]#主件
fu={}#附件，键存储主件编号，值存储每一个附件
for i in range(m):#分别存储主件和附件
    if a[i][2]==0:#是主件
        zhu.append(a[i]+[i+1])#将主件编号附在后面
    else:#是附件
        if a[i][2] in fu:#附件编号已经存在
            fu[a[i][2]].append(a[i])#添加第二个新的附件
        else:
            fu[a[i][2]]=[a[i]]#添加第一个新的附件
size1=len(zhu)#物品数量
dp=[[0 for i in range(n+1)] for j in range(size1)]#注意钱数要开n+1，这样下标才能到n
for i in range(0,n+1):#初始化第一行,遍历钱数
    idx=zhu[0][3]#第一行对应的物品的主件编号
    if idx in fu:#如果第一行这个主件有附件
        if len(fu[idx])==1:#长度为1，只有一个附件，枚举单主件、主件+附件
            if i>=zhu[0][0]:
                dp[0][i]=zhu[0][0]*zhu[0][1]
            if i>=zhu[0][0]+fu[idx][0][0]:
                dp[0][i]=zhu[0][0]*zhu[0][1]+fu[idx][0][0]*fu[idx][0][1]
        else:#长度为2，枚举单主件，max(主件+附件1,主件+附件2),主件+附件1+附件2
            if i>=zhu[0][0]:
                dp[0][i]=zhu[0][0]*zhu[0][1]
            if i>=zhu[0][0]+fu[idx][0][0]:#主件+附件1
                dp[0][i]=max(dp[0][i],zhu[0][0]*zhu[0][1]+fu[idx][0][0]*fu[idx][0][1])
            if i>=zhu[0][0]+fu[idx][1][0]:#主件+附件2
                dp[0][i]=max(dp[0][i],zhu[0][0]*zhu[0][1]+fu[idx][1][0]*fu[idx][1][1])
            if i>=zhu[0][0]+fu[idx][0][0]+fu[idx][1][0]:#主件+附件1+附件2
                dp[0][i]=zhu[0][0]*zhu[0][1]+fu[idx][1][0]*fu[idx][1][1]+fu[idx][0][0]*fu[idx][0][1]
    else:
        if i>=zhu[0][0]:
            dp[0][i]=zhu[0][0]*zhu[0][1]
for i in range(1,len(zhu)):#遍历主件
    for j in range(0,n+1):#遍历钱数
        if j<zhu[i][0]:#买不起
            dp[i][j]=dp[i-1][j]
        else:
            idx=zhu[i][3]#此主件的编号
            if  idx in fu:#有附件
                if len(fu[idx])==1:#长度为1，枚举单主件、主件+附件
                    vi=zhu[i][0]
                    wi=zhu[i][0]*zhu[i][1]
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-vi]+wi)#比较不拿此主件和拿此主件哪个大
                    if j>=zhu[i][0]+fu[idx][0][0]:
                        vi=zhu[i][0]+fu[idx][0][0]
                        wi=zhu[i][0]*zhu[i][1]+fu[idx][0][0]*fu[idx][0][1]
                    dp[i][j]=max(dp[i][j],dp[i-1][j-vi]+wi)#如果拿主件+附件更大那就更新
                else:#长度为2，枚举单主件，max(主件+附件1,主件+附件2),主件+附件1+附件2
                    vi=zhu[i][0]
                    wi=zhu[i][0]*zhu[i][1]
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-vi]+wi)
                    if j>=zhu[i][0]+fu[idx][0][0]:#主件+附件1
                        vi=zhu[i][0]+fu[idx][0][0]
                        wi=zhu[i][0]*zhu[i][1]+fu[idx][0][0]*fu[idx][0][1]
                        dp[i][j]=max(dp[i][j],dp[i-1][j-vi]+wi)
                    if j>=zhu[i][0]+fu[idx][1][0]:#主件+附件2
                        vi=zhu[i][0]+fu[idx][1][0]
                        wi=zhu[i][0]*zhu[i][1]+fu[idx][1][0]*fu[idx][1][1]
                        dp[i][j]=max(dp[i][j],dp[i-1][j-vi]+wi)
                    if j>=zhu[i][0]+fu[idx][0][0]+fu[idx][1][0]:#主件+附件1+附件2
                        vi=zhu[i][0]+fu[idx][0][0]+fu[idx][1][0]
                        wi=zhu[i][0]*zhu[i][1]+fu[idx][0][0]*fu[idx][0][1]+fu[idx][1][0]*fu[idx][1][1]
                        dp[i][j]=max(dp[i][j],dp[i-1][j-vi]+wi)
            else:#没有附件，只讨论主件取或不取
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-zhu[i][0]]+zhu[i][0]*zhu[i][1])
print(dp[size1-1][n])