问题
顺丰速运，全货机专机运输，提供高效的便捷服务，更快更安全!
首先，是快捷的时效服务。自有专机和400余条航线的强大航空资源以及庞大的地面运输网络，保障客户的快递在各环节最快发运。
其次，是安全的运输服务。顺丰速运自营的运输网络，给消费者提供标准、高质、安全的服务。
由此，顺丰速运在消费者的心中留下了完美的形象，从而提高了企业的业绩，也奠定了其在整个快递领域中的基础。
顺丰快递每天能收到成千上万的物流单，每个物流单的重量不一。 现在顺丰快递的货车司机隔壁老王开着顺丰的标配货车（限载5吨，含5吨，不考虑限高）,想要一次性拿走尽可能重的货物，这些货有红木沙发，有钢材等等。
以下是货物清单：货物编号 货物重量(单位:kg) 1 509 2 838 3 924 4 650 5 604 6 793 7 564 8 651 9 697 10 649 11 747 12 787 13 701 14 605 15 644比如1-2-3代表同时装入编号为1,2,3的货物，此时货物总重为509（1号货物）+838（2号货物）+924（3号货物）=2271kg,远小于限载额——5吨，隔壁老王会被吐槽的。
比如1-5-8-9-11-12-14代表同时装入编号为1,5,8,9,11,12,14的货物，此时货物总重为509（1号货物）+604（5号货物）+651（8号货物）+697（9号货物）747（11号货物）+787（12号货物）+605（14号货物）=4600kg，这时与限载额5吨就比较接近了，隔壁老王会很高兴……
理解动态规划
首先我们分析装货问题，我们需要找到的是最优化的装货方案，即排列组合问题。在当前的问题中，我们可以将排列组合问题简化。简化为，对每一个货物进行讨论，讨论当前货物是装还是不装，并将之后商品的讨论交给递归。现在问题变成，给递归设置判断条件和边界。
- 判断条件是“装”和“不装”，返回更大的总重量。
- 边界是当列表仅剩下一个货物时，不进入递归直接返回货物重量或0。
由于我们的判断条件为剩余可携带重量，所以我们并不能从递归的结果得到货物的组合方式，得到的结果是可携带的最大重量。所以我们可以使用itertools来实现货物的遍历。
这里可能会发现，我们完全可以在排列组合中进行判断可携带的最大重量，为什么还要用递归这种复杂的方法。在我的测试下，我在原本的货物重量列表中，添加了这些新的重量“509,838,924,650,604,20,23,40”，如此一来计算量大了两个数量级递归的循环次数达到800多万，这时递归的函数调用次数和循环次数在500多万。在递归中，存在相同子查询舍弃的情况，所以待筛选元素越多，排列组合的效率是越低的。
解题
以下为学习了动态规划，并且参考了WeaponX的代码之后用python实现的解题程序。
import itertools
class laowang:
def __init__(self):
#老王可以选择货物的重量
self.goods = [509,838,924,650,604,793,564,651,697,649,747,787,701,605,644]
#老王的车可以放置的最大重量
self.max_weight = 5000
#动态规划
self.fun2()
#排列组合
self.fun1()
def fun1(self):
print('排列组合')
self.count = 0
result2 = 0
#排列组合寻找选择结果
for i in range(len(self.goods)):
for x in itertools.combinations(self.goods,i):
self.count += 1
if sum(x) > result2 and sum(x)<=self.max_weight:
result2 = sum(x)
result_list = x
print(result2,result_list,self.count)
def fun2(self):
print('动态规划')
self.count = 0
#计算可以带走的最大的重量
result = self.getmax(self.max_weight, len(self.goods) - 1)
print(result,'getmax() count:',self.count)
self.count = 0
# 排列组合寻找选择结果
for i in range(len(self.goods)):
for x in itertools.combinations(self.goods,i):
self.count += 1
if sum(x) == result:
print(x,'-'.join([str(self.goods.index(o)+1) for o in x]),'for count:',self.count)
def getmax(self, last_weight, item):
self.count += 1
#如果当前只剩下一个（边界）
if item == 0:
#剩余重量大于当前货物重量，返回当前货物重量
if last_weight >= self.goods[item]:
return self.goods[item]
else:
return 0
#方案a：如果剩余重量大于当前货物重量，那么带走，不大于，那么planA为0
if last_weight > self.goods[item]:
plan_a = self.getmax(last_weight - self.goods[item], item - 1) + self.goods[item]
else:
#由于无法带走当前货物，所以与planB等价，防止重复搜索，planA=0
plan_a = 0
#方案b：放弃当前货物，直接到下一个货物
plan_b = self.getmax(last_weight, item - 1)
#挑选重量更高的方案，返回
if plan_a > plan_b:
return plan_a
else:
return plan_b
if __name__ == '__main__':
laowang()运行结果
