淮南师范学院-货物运输算法(最终版)课程设计.docVIP

学号 0908210131 《计算机算法设计》 课程设计报告 题目： 货物运输 专业： 计算机科学与技术 班级： 计算机科学与技术 姓名： 璩勇 指导教师： 江涛 成绩： 计算机与信息工程系 2013年 4月 25日 目录 1 设计内容及要求 3 2 算法原理 3 3 算法设计 4 3.1 动态规划法： 4 3.2 分支界限法： 5 3.3详细设计 5 3.4 算法编码实现 6 4 算法分析 15 5 运行结果 15 5.1测试数据 15 5.2测试结果 15 6 参考文献 17 设计题目：货物运输 设计内容及要求 1.1 在杂货店中有n 种不同的货物。现将货物装车规定从每种货物中最多只能拿一件，卡车的容量为c，物品i 需占用wi 的空间，价值为pi 。现要求设计算法和程序使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。 算法原理 动态规划法是上世纪 50年代Richard Bellman创建的解决多阶段决策过程最优化的一种数学方法，即把多阶段决策问题变换为一系列相互联系单阶段问题，然后逐个加以解决。它的特点是解决多阶段、离散性问题。动态规划算法的基本思想是把原问题分解成一系列子问题,然后从这些子问题中求出原问题的解。 对一个负重能力为 C 的货车,如果选择装入第 i 种物品,那么原货车问题就转化为负重能力为 C-ci的子货车问题。动态规划算法是一种经典的货车问题求解算法，其原理简单，算法思路清晰，易于实现。动态规划算法虽然高效，但是对于规模较大的问题它不是一个理想的算法，主要原因就是它的维数障碍，即计算和存储量的需要对于状态空间和决策空间的维数的增长呈指数增长关系。动态规划算法的时间复杂度为 o(min(n·C，2^n)),其中 n 为物体的个数,C为货车负重。 精确算法的优点是当问题规模较小时一定可以求得最优解， 缺点是当问题规模较大时因计算量太大而无法实现。 所以一些学者提出了各种近似算法来解决精确算法求解货车问题时的时间复杂性和空间复杂性难题。 算法设计 本实验主要是运用动态规划法和分支界限法解0/1货车问题。算法分析如下： 3.1 动态规划法： 我们可以把前i个物品中能够放进承重量为j的货车中的子集分成两个类别：包括第i个物品的子集和不包括第i个物品的子集。有下结论： 根据定义，在不包括第i个物品的子集中，最优子集的价值是V[i-1,j]。 在包括第i个物品的子集中（因此，j-Wi=0），最优子集是由该物品和前i-1个物品中能够放进承重量为j-Wi的货车的最优子集组成。这种最优子集的总价值等于vi+V[i-1,j-wi]. 因此，在前i个物品中最优解的总价值等于这两个价值中的较大值。当然，如果第i个物品不能放进货车，从前i个物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值。这个结果导致了下面这个递推式： V[i,j]=max{V[i-1,j],vi+V[i-1,j-wi]},j-wi=0或者 V[i,j]=V[i-1,j],j-wi0。 我们可以很容易的正阳定义初始条件： 当j=0时，V[0,j]=0;当i=0时，V[i,0]=0。 我们的目标是求V[n,W]，即n个给定物品中能够放进承重量为W的货车的子集的最大总价值，以及最优子集本身。 3.2 分支界限法： 分支界限法主要是按任意方式建立如下次序： ? 计算上界ub的一个简单方法是，把已经选择物品的总价值v，加上货车的剩余承重量W-w与剩下物品的最佳单位回报 的积： 然后根据分支界限法的基本思想即可求出该0/1货车问题的最优解了。 3.3详细设计 本次试验程序主要用到两个算法，分别是动态规划算法和分支界限算法，其货车问题模块流程图如下： 图1 货车问题模块流程图 货车问题程序流程图大致如下： 图2 货车问题程序流程图 该图很直观的描述了整个程序操作过程。 3.4 算法编码实现 动态规划法： #include iostream using namespace std; class beibao { private: int W;//W为卡车的承重量 int n;//n为物品的数量 int c[20][100]; int w[20]; int v[20]; int x[20]; public: void input(); void suanfa(); int* display(); };