基于动态规划的商品装载问题及JAVA 实现

顾桓瑜

摘要：如何装载商品使经济利益最大化是物流配载装箱问题中划分出的子问题。该子问题被抽象为0-1背包问题，根据动态规划算法建立数学模型，分析其优点，并用JAVA语言得以实现。最后给出测试实例，得出动态规划法具有高效性的特点，该算法可以广泛使用于物流领域。

关键词：动态规划；装载问题；JAVA语言

中图分类号：TP31 文献标识码：A 文章编号：1009-3044（2014）10-2401-03

Abstract： How to load goods to get maximum economic benefits by manufacturers is a sub-problem divided from logistics distribution.In this paper，the sub-problem is abstracted a 0-1 knapsack problem.We create a mathematical model based on dynamic programming algorithm，and analyze the advantages of the algorithm.Then we use JAVA language to solve the problem.After setting some test datum， the final results show that the dynamic programming method has efficiency，and can be applied widely.

Key words： Dynamic programming； Loading problems； JAVA language

随着经济的不断发展，各厂商在满足客户需求的条件下，利用物流技术，从备货、装箱、配送、存储等物流配载技术网中寻求省时省力的方法，使得资源使用效率得到提高，同时降低了厂商的成本[1]。

问题提出：某厂商每周向校园超市运输一次商品，在小型货车容量不变且不能超载的约束下，如何装载商品，使产生的经济效益最大化？该问题是厂家所关心的，也是本文的关注点。运用动态规划方法解决此问题，能够较好地控制企业的人力资源成本和运输成本，从而提高商业的竞争力。

1 动态规划算法简介

动态规划（dynamic programming）[2]产生于20世纪50年代，由美国数学家R.E.Bellman等人提出。动态规划的思想是把一个问题划分为具有相关性的若干子问题来解决，并将各个子问题求解答案和求解方法进行保存。如果在之后的处理过程中还需要用到已解决的子问题，则直接调用答案，从而避免重复的计算，节省了时间。

在解决实际问题中，我们需要动态规划出适当的约束条件和递推关系，并在各单阶段中寻找互相联系的因素，依次将每一阶段所得的最优结果进行存储。这种阶段划分、自下向上的求解方式需要建立表或数组才能有效实施。如图1所示：

基于动态规划法解决的问题需要满足一定的条件，例如：（1）满足无后效性，即子问题的下一状态只与现在状态有关；（2）满足最优性子结构，得出子问题的最优解；（3）原问题可以划分出多个拥有关联的子问题[3]。

2 模型的建立

厂商向校园超市运输商品的问题：已知厂商共有N件商品，每件商品拥有固定的Id号，Id=i的商品重量为Wi，产生的经济效益为Vi，货车的最大载重量为N。现假设一个n维向量Xi=（X1，X2，...Xn）∈{0，1}n，当Xi=1时表明相应Id的商品装入车中；当Xi=0时表明商品未装入车中。最终得出的结果为[maxi=1nViXi]，即最大效益值，约束条件为[maxi=1nWiXi]≤N。货车的载重量是有限的，在这个上限内尽可能装下商品使经济效益越高越好。通过以上分析，此问题恰好可以抽象为一个重量集合、经济效益集合与货车载重量分别是Wi={W1，W2，...Wn}，Vi={V1，V2，...Vn}和N的0-1KP问题。

在0-1背包问题中，物品价值与体积不随背包容量的变化而变化[4]。举例说明：假设有N=3个物品，总容量为10，体积V[i]={2，4，6}分别对应价值P[i]={3，7，4}，设数组B[i][j]，表示在背包容量为j的条件下，放入第i个物品后的最大价值。如下表1所示：

动态规划算法易于编程的实现，虽然需要一定的空间存储其产生的结果，但是它的高效性能在测试中体现出来。

4 测试数据

假设厂商货车载重量为上述的1534，他们所建Commodity表中总共有50件商品，其Id、weight、value的数据分别如下所示：

最终得出经济效益最大值为1904，如图3所示。

5 结束语

本文从实际出发，给出厂商向校园超市运输商品时的装载问题，结合一个有效的算法——动态规划算法，利用JAVA语言得以实现。动态规划法有较好的效率和速度，不仅能用于解决装箱问题，而且能够运用于物流配载中的路径规划、资源分配等实际问题，优化了企业资源管理，提高经济效益，降低资源成本，能够应用于更多的科学领域中。

参考文献：

[1] 谢天保，雷西玲，席文玲.物流配送中心配载车辆调度问题研究[J].计算机工程与应用，2010，36：237-240.

[2] 陈大伟，孙瑞志，向勇，史银雪.基于流程模式的工作流静态规划方法[J].计算机工程与设计，2011（1）：129-132，137.

[3] 厉洋峰.动态规划及其在数学模型中的应用[J].中国新技术新产品，2009（16）：244-245.

[4] 王凌，王圣尧，方晨.一种求解多维背包问题的混合分布估计算法[J].控制与决策，2011（8）：1121-1125.