回溯算法——0-1背包问题.doc

实验目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 上机实验一般应包括以下几个步骤： （1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。 （2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。 （3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。 实验八 回溯算法——0-1背包问题 一、实验目的与要求 1. 熟悉0-1背包问题的回溯算法。 2. 掌握回溯算法。 二、实验内容 用回溯算法求解下列“0-1背包”问题： 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物???的总价值最大? 三、实验步骤 1. 理解算法思想和问题要求； 2. 编程实现题目要求； 3. 上机输入和调试自己所编的程序； 4. 验证分析实验结果； 5. 整理出实验报告。 实验提示： （1）回溯算法求解0-1背包问题分析 回溯法通过系统地搜索一个问题的解空间来得到问题的解。为了实现回溯，首先需要针对所给问题，定义其解空间。这个解空间必须至少包含问题的一个解（可能是最优的）。 然后组织解空间。确定易于搜索的解空间结构。典型的组织方法是图或树。一旦定义了解空间的组织方法，即可按照深度优先策略从开始结点出发搜索解空间。并在搜索过程中利用约束函数在扩展结点处剪去不满足约束的子树，用目标函数剪去得不到最优解的子树，避免无效搜索。用回溯法解题的步骤： 1）针对所给问题定义问题的解空间； 2）确定易于搜索的解空间结构； 3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效的搜索。 0-1背包问题的数学描述为：n个物品，物品i的重量是wi、其价值为vi，其中0≤i≤n-1，背包的容量为C。用xi表示物品i被装入背包的情况，如果物品Pi被选中，则xi=1；否则xi=0。求满足目标函数和约束方程的物品组合（x0，x1，x2，…，xn-1) 与相应的总价值V。 1）针对所给问题定义问题的解空间。 根据上述0-1背包问题的数学描述，解向量可以表示成X={ x0，x1，x2，…，xn-1) | xi=1或xi=0} 。若n = 3 ， 则此0-1背包问题的解空间为 {(0，0，0)，(0，0，1) ，(0，1，0)，(0，1，1)，(1，0，0)，(1，0，1)，(1，1，0)，(1，1，1)}。 2）确定易于搜索的解空间结构。 可以用树的形式将解空间表达出来。树中从第i层到第i+1层的边上的值表示解向量中xi的取值，并假定第i层的左子树描述物品Pi被装入背包的情况，右子树描述物品Pi被拒绝的情况。则该0-1背包问题的状态空间树就表示为一棵高度为n的完全二叉树（如图l所示) 。从根结点到叶子结点的任一路径就对应解空间中的一个解向量。 3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效的搜索。 构造出问题的状态空间树以后，就可以从其根结点出发搜索解空间，即决定每个物品的取舍。为了使目标函数的值增加最快，可以优先选择价值最大的物品装入背包，然后是价值量次之的物品，……，直至背包装不下为止。但是，如果所选择的物品重量很大，使得背包载重量消耗速度太快，以至后续能装入背包的物品迅速减少，使得继续装入背包的物品在满足了约束方程的要求以后，无法达到目标函数的要求。因此，最好优先选择那些既使目标函数的值增加最快。又能使背包载重量消耗速度较慢的物品装入背包。为了达到这个目的，首先把所有物品按价值重量比的非增顺序排列，然后按照这个顺序进行搜索。在装包过程中， 要尽量优先选择价值重量比较高的物品装入背包。表现在搜索过程中，就是要尽量沿着左子树结点前进。当不能继续前进时（假设该结点为T），就得到问题的一个部分解，并把搜索转移到右子树。估计由该部分解所能得到的最大价值，即结点T的上限。可以用贪婪算法处理剩余物品：将按照价值重量比非增顺序排列的剩余物品依次装入背包，至无法完全装入下一个物品时，就将该物品的一部分装满背包。这样就可以得到一个上限。如果该值为当前最优值：继续由右子树向下搜索，扩大部分解，直至找到可行解；保存可行解，并把可行解的值作为当前最优值，向上回溯，寻找其他可行解；若该值小于当前最优值：丢弃当前正在搜索的部分解，向上回溯。反复使用此方法，直至搜索完整个解空间。 （2）回溯算法求解0-1背包问题示例： 给定8种物品和一个背包。8种物品的重量和价值分别为（79，83）、（58，14）、（86，54）、（11，79）、（28，72）、（62，52）、（15，48）、（68，62），背包的容量为