moozik

【千里码】老王装货问题,动态规划的实现
问题顺丰速运,全货机专机运输,提供高效的便捷服务,更快更安全!首先,是快捷的时效服务。自有专机和400余条航线的强...
扫描右侧二维码阅读全文
20
2017/01

【千里码】老王装货问题,动态规划的实现

问题

顺丰速运,全货机专机运输,提供高效的便捷服务,更快更安全!
首先,是快捷的时效服务。自有专机和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()

运行结果

附录

千里码-老王装货

千里码-老王装货的学习资料

通过金矿模型介绍动态规划

最后修改:2017 年 12 月 06 日 02 : 01 PM

发表评论