题解 | 动态规划python3#购物单#
购物单
http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
这一题真的花了我好长时间！！！这一题是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
- 单价价格表（相当于背包问题的重量，限制我们总金额）W[i]=v
（注意：该编号为主件编号，不一定从1 开始，不是列表的index）
| 编号 | 主件 | 附件1 | 附件2 |
|---|---|---|---|
| 3 | 10 | 0 | 0 |
| 4 | 10 | 0 | 0 |
| 5 | 10 | 20 | 20 |
- 价值表（每个主、附件对应的价值，我们要求的让他们和最大的值）V[i]=p*v
| 编号 | 主件 | 附件1 | 附件2 |
|---|---|---|---|
| 3 | 30 | 0 | 0 |
| 4 | 20 | 0 | 0 |
| 5 | 10 | 60 | 60 |
接下来就以该表为基础建立动态规划表格：
列：主件m
行：总金额N
dp = [[0]*(m+1) for _ in range(N+1)] (第一行初始值为0）
那么每一行（每个主件）有5种投放效果：
- 不放主件
- 只放主件
- 主件+附件1
- 主件+附件2
- 主件+附件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
