题解 | 动态规划python3#购物单#

这一题真的花了我好长时间！！！这一题是01背包问题的衍生，但是多了一个附件的判断，导致这道题很琐碎要考虑很多细节。（感觉要是机考考这道题我完全做不完了）

前提知识背景：01背包问题 （不知道这道题怎么做的可以先把01背包问题看懂https://zhuanlan.zhihu.com/p/104738622）

本题：

重点是如何处理附件问题。我们可以先把自己所得的数据进行分类（分为两个表格）：

所得数据（举例）：

50 5

20 3 5

20 3 5

10 3 0

10 2 0

10 1 0

1. 单价价格表（相当于背包问题的重量，限制我们总金额）W[i]=v

（注意：该编号为主件编号，不一定从1 开始，不是列表的index）

2. 价值表（每个主、附件对应的价值，我们要求的让他们和最大的值）V[i]=p*v

接下来就以该表为基础建立动态规划表格：

列：主件m

行：总金额N

dp = [[0]*(m+1) for _ in range(N+1)] (第一行初始值为0）

那么每一行（每个主件）有5种投放效果：

1. 不放主件
2. 只放主件
3. 主件+附件1
4. 主件+附件2
5. 主件+附件1+附件2

那么每行dp[i][j]=max(5种情况） 取最大值

建立2D动态规划方程：

dp = [[0]*(total+1) for _ in range(m+1)]
for i in range(m+1):
  for j in range(total+1):
      dp[i][j] =dp[i-1][j]
      if j-w1>=0:
          dp[i][j] = max(dp[i][j],dp[i-1][j-w1]+v1)
      if j-w1-w2>=0:
          dp[i][j] = max(dp[i][j], dp[i-1][j-w2-w1]+v1+v2)
      if j-w1-w3>=0:
          dp[i][j] =  max(dp[i][j], dp[i-1][j-w3-w1]+v1+v3)
      if j-w1-w2-w3 >=0:
          dp[i][j] =  max(dp[i][j], dp[i-1][j-w3-w2-w1]+v1+v2+v3)

可以进一步压缩空间，变成1D数组进行滚动：

(这里需要注意for循环顺序和上面相反！！！）

因为dp[j]依赖于其左侧元素的值，如果我们从左往右进行循环的话，会先更新左侧元素dp[j-w[i]]，这样当我们计算到dp[j]的时候，dp[j-w[i]]已经是最新的值（可以理解为dp[i][j-w[i]]），并不是我们想要的“上一行”的值（可以理解为我们想要的是dp[i-1][j-w[i]]）。因此，正确的做法是，从右往左进行循环。

dp = [0 for _ in range(total+1)]
for i in range(1，m+1):
  for j in range(total,-1,-1):
      dp[j] =dp[j]
      if j-w1>=0:
          dp[j] = max(dp[j],dp[j-w1]+v1)
      if j-w1-w2>=0:
          dp[j] = max(dp[j], dp[j-w2-w1]+v1+v2)
      if j-w1-w3>=0:
          dp[j] =  max(dp[j], dp[j-w3-w1]+v1+v3)
      if j-w1-w2-w3 >=0:
          dp[j] =  max(dp[j], dp[j-w3-w2-w1]+v1+v2+v3)

完整代码：

while True:
    try:
        # 金额限制总价，物品数量
        total,k = list(map(int,input().split(" ")))
        ## 单价
        W = {}
        ## 单价* 重要程度=价值
        V = {}
        # 因为价格是10的倍数，为方便运算，价格/10
        total = int(total/10)
        # 主件个数
        main_key = []
        # 构造字典
        for i in range(1,k+1):
            W[i]=[0,0,0]
            V[i]=[0,0,0]
        for i in range(k):
            # 单价，重要程度，类别
            v,p,q = list(map(int,input().split(" ")))
            if q == 0:
                W[i+1][0] = int(v/10)
                V[i+1][0] = int(v*p/10)
                main_key.append(i+1)
            else:
                if W[q][1]==0:
                    W[q][1] = int(v/10)
                    V[q][1] = int(v*p/10)
                else:
                    W[q][2] = int(v/10)
                    V[q][2] = int(v*p/10)
        W_lst = []
        V_lst = []
        for key in W.keys():
            if key in main_key:
                W_lst.append(W[key])
                V_lst.append(V[key])
        m = len(W_lst)
        # 构造二维数
        dp = [[0]*(total+1) for _ in range(m+1)]
        for i in range(1,m+1):
            w1 = W_lst[i-1][0]
            w2 = W_lst[i-1][1]
            w3 = W_lst[i-1][2]
            v1 = V_lst[i-1][0]
            v2 = V_lst[i-1][1]
            v3 = V_lst[i-1][2]
            for j in range(total+1):
                # 1. 不放入:
                dp[i][j] =dp[i-1][j]
                # 2. 放入一个主件
                if j-w1>=0:
                    dp[i][j] = max(dp[i][j],dp[i-1][j-w1]+v1)
                # 3. 1个主件+附件1
                if j-w1-w2>=0:
                    dp[i][j] = max(dp[i][j], dp[i-1][j-w2-w1]+v1+v2)
                # 4. 一个主件+附件2
                if j-w1-w3>=0:
                    dp[i][j] =  max(dp[i][j], dp[i-1][j-w3-w1]+v1+v3)
                # 5. 一个主见+附件1+附件2
                if j-w1-w2-w3 >=0:
                    dp[i][j] =  max(dp[i][j], dp[i-1][j-w3-w2-w1]+v1+v2+v3)
        print(int(dp[m][total]*10))
    except:
        break