背包问题-动态规划-购物单
购物单
http://www.nowcoder.com/questionTerminal/f9c6f980eeec43ef85be20755ddbeaf4
动态规划问题，前面有很多答案，我这里采用一个记录路径的方式解决。优点是有的时候动态规划的题目会同时让你输出具体的过程信息，那么这种方式就很直观，也方便排错。
设dp[n][0]为花了n元钱共获得的总价值，即v1*p1+v2*p2+...；
而dp[n][1]记录被选择的物品编号列表。物品个数最大只有60个，所以此列表并不需要进行优化。若进行优化，则优化方式可以利用二进制位操作记录整数的方式等等。利用python对列表应用的特性，就可以方便的判断某个数是否在列表中，即dp[n][1]是否包含当前的物品编号（或当前物品的q值，即父亲物品编号）。
虽然数组（Python中是列表）是二维，但动态规划其实只是一维动态规划，即完全可以把dp[n][1]单独用另一个数组记录。受益于Python的灵活性，此处用一个可变的列表进行记录操作。
那么对于总价值最优判断就有两个可能性：
1。当前物品的父物品q已经被选择，那么就考虑放入当前物品后，价值是否更大，即(dp[i-v][0]+v*p)>dp[i][0]；
2。当前物品的父物品q没有被选择，那么就考虑两个物品都放入，价值是否更大，即(dp[i-v-parent_v][0]+v*p+q_v*q_p)>dp[i][0]，其中q_v和q_p代表父物品q的价值v和重要度p。当然，前提是当前物品没有被重复放入，且父亲物品q之前也没有被放入。
之所以要进行第二个可能性的考虑，是因为对数组进行遍历修改取优值的时候，必须保证每种物品都可以在不依赖遍历顺序的前提下有选择的放入背包，也就是普通的0-1背包问题。不管你是先从第一个物品开始选，还是最后一个物品，还是中间某个物品，都不会对结果产生影响。
而这里，如果你遍历物品按照输入的顺序，有可能出现子物品先入库，而父物品还没有入库的情形，从而造成此子物品由于父物品还未纳入考虑，而完全不可能被选择的情况。
解决这种有条件性的问题，就是列出可能让他放入的各种条件。这也就是很多人考虑父子物品的时候，干脆都按照同等地位的物品进行考虑，也即父物品单独入库，父+子物品，父+子2物品，父+子3物品，父+子1+子2， 父+子2+子3，父+子1+子3。。。这样使每种子物品变成了父+子物品的绑定形态。而题目中限定了子物品的个数为2，所以只需要列举父物品单独选择，父+子1物品，父+子2物品和父+子1+子2这几种可能性。相比之下，我的想法在子物品过多的情况下，会更容易。因为任何一种子物品入库，都可以只去考虑他的父物品，而不再需要考虑他的兄弟物品是否入库的情形。
除此之外，对动态规划永远都用倒序遍历，同时记得判断下标不要越界，没IDE的时候多写几个if判断界限不丢人。
用例100%通过。
while True:
try:
total_money,total_num=map(int,input().split(' '))
total_money//=10
product_item=[]
for i in range(total_num):
v,p,q=map(int,input().split(' '))
v//=10
product_item+=[[i+1,v,p,q]]
dp=[[0,[0]] for i in range(total_money+1)]
for current_no,v,p,q in product_item:
for i in range(len(dp)-1,-1,-1):
if (i-v)>=0:
if not current_no in dp[i-v][1]:
if q in dp[i-v][1]: # the parent has been chosen.
if (dp[i-v][0]+v*p)>dp[i][0]:
dp[i][0]=dp[i-v][0]+v*p
dp[i][1]=dp[i-v][1].copy()
dp[i][1]+=[current_no]
else: # the parent has not been chosen, then we can pick up both current one and the parent.
if (i-v-product_item[q-1][1])>0:
if (dp[i-v-product_item[q-1][1]][0]+v*p+product_item[q-1][1]*product_item[q-1][2])>dp[i][0] and not current_no in dp[i-v-product_item[q-1][1]][1] and not q in dp[i-v-product_item[q-1][1]][1]:
dp[i][0]=dp[i-v-product_item[q-1][1]][0]+v*p+product_item[q-1][1]*product_item[q-1][2]
dp[i][1]=dp[i-v-product_item[q-1][1]][1].copy()
dp[i][1]+=[current_no]
dp[i][1]+=[q]
print(dp[total_money][0]*10)
except:
break 
投递百度等公司10个岗位 >
