《回溯算法——0-1背包问题.docx》由会员分享，可在线阅读，更多相关《回溯算法——0-1背包问题.docx（6页珍藏版）》请在三一文库上搜索。
1、实验目的是使学生消化理论知识，加深对讲授内容的理解， 尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：(1) 、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。(2) 、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题, 最好独立解决。(3) 、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、 对运行情况所作的分析。实验八回溯算法一一0-1背包问题一、实验目的与要求1. 熟悉0-1背包问题的回溯算法。2. 掌握回溯算法。二、实验内容用回溯算法
2、求解下列“ 0-1背包”问题：给定n种物品和一个背包。物品 i的重量是Wi,其价值为Vi,背包的容量为 Co问应如 何选择装入背包的物品，使得装入背包中物品的总价值最大？三、实验步骤1. 理解算法思想和问题要求；2. 编程实现题目要求；3. 上机输入和调试自己所编的程序；4. 验证分析实验结果；5. 整理出实验报告。实验提不':(1) 回溯算法求解0-1背包问题分析回溯法通过系统地搜索一个问题的解空间来得到问题的解。为了实现回溯，首先需要针对所给问题，定义其解空间。这个解空间必须至少包含问题的一个解(可能是最优的)。然后组织解空间。确定易于搜索的解空间结构。典型的组织方法是图或树。一旦
3、定义了解空间的组织方法，即可按照深度优先策略从开始结点出发搜索解空间。并在搜索过程中利用约束函数在扩展结点处剪去不满足约束的子树，用目标函数剪去得不到最优解的子树，避免无效搜索。用回溯法解题的步骤：1) 针对所给问题定义问题的解空间；2) 确定易于搜索的解空间结构；3) 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效的搜索。0-1背包问题的数学描述为：n个物品，物品i的重量是wi、其价值为V,其中0<i<n-1,背包的容量为 C。用Xi表示物品i被装入背包的情况，如果物品Pi被选中，贝U为=1；否则Xi=0。求满足目标函数 F =max£为乂 Vi和约束方程Z
4、 x< w C的物品组合(x°, i =0i =0X1, X2,，Xn-1)与相应的总价值 V。1） 针对所给问题定义问题的解空间。根据上述0-1背包问题的数学描述，解向量可以表示成X=（ X 0, Xi, 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层的边上的值表示解向量
5、中Xi的取值，并假定第i层的左子树描述物品 Pi被装入背包的情况，右子树描述物品Pi被拒绝的情况。则该0-1背包问题的状态空间树就表示为一棵高度为n的完全二叉树（如图l所示）。从根结点到叶子结点的任一路径就对应解空间中的一个解向量。图1时0T背包何题的状态空间树3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效的搜索。构造出问题的状态空间树以后，就可以从其根结点出发搜索解空间，即决定每个物品的取舍。为了使目标函数的值增加最快，可以优先选择价值最大的物品装入背包，然后是价值量次之的物品，直至背包装不下为止。但是，如果所选择的物品重量很大，使得背包 载重量消耗速度太快，以至后续能装入背
6、包的物品迅速减少，使得继续装入背包的物品在满足了约束方程的要求以后，无法达到目标函数的要求。因此，最好优先选择那些既使目标函 数的值增加最快。又能使背包载重量消耗速度较慢的物品装入背包。为了达到这个目的， 首先把所有物品按价值重量比的非增顺序排列，然后按照这个顺序进行搜索。在装包过程中， 要尽量优先选择价值重量比较高的物品装入背包。表现在搜索过程中，就是要尽量沿着左子树结点前进。当不能继续前进时（假设该结点为T）,就得到问题的一个部分解，并把搜索转移到右子树。估计由该部分解所能得到的最大价值，即结点T的上限。可以用贪婪算法处理剩余物品：将按照价值重量比非增顺序排列的剩余物品依次装入背包，至无法
7、完全装入下一个物品时，就将该物品的一部分装满背包。这样就可以得到一个上限。 如果该值为当前最优值：继续由右子树向下搜索，扩大部分解，直至找到可行解；保存可行解，并把可行解 的值作为当前最优值，向上回溯，寻找其他可行解；若该值小于当前最优值：丢弃当前正在 搜索的部分解，向上回溯。反复使用此方法，直至搜索完整个解空间。（2）回溯算法求解0-1背包问题示例：给定8种物品和一个背包。8种物品的重量和价值分别为（79, 83）、（58, 14）、（86, 54）、（11, 79）、（28, 72）、（62, 52）、（15, 48）、（68, 62），背包的容量为 200。问应如 何选择装入背包的物品，
8、使得装入背包中物品的总价值最大？一种可能的解决方案是（红色字体强调突出的物品）(79, 83)、(58, 14)、(86, 54)、(11, 79)、(28, 72)、(62 , 52)、(15, 48)、(68, 62);装入背包中的物品的总价值为334。(3) 回溯算法求解0-1背包问题的源代码(供参考)算法步骤如下：1) 按价值重量比的非增顺序排列物品。2) 初始化：当前背包重量 tempW为0,当前背包中物品总价值 tempV为0,当前搜索 深度i为0,当前解向量为xi=0，当前最优值 maxV为0。3) 调用限界函数。4) 如果返回的上限大于当前最优值maxV，从物品Pi开始把物品装
9、入背包，直至没有物品可装或装不下物品 Pk为止，并生成部分解，转步骤5);否则，转步骤 6)。5) 如果k大于或等于物品总数量n,则得到一个可行解，并把该可行解的值作为当前最优值，令i=n,转步骤3),以便回溯搜索其他可行解；否则，令 i=k+l，拒绝物品k,从物 品k+l继续装入，转步骤 3 )。6) 当k > 0且xk=0时，令k=k-1 ,直至条件不成立。即沿着右分支结点方向向上回溯， 直至左分支结点。7) 如果k<0,算法结束；否则，转步骤8)。8) 令 xk=0 , tempW=tempW-wk , tempV=tempV-vk , i=k+l，转步骤 3)。/*回溯法解
10、0-1背包问题*/#define N 8 / 物品个数#define C 200 / 容积int resultN; /存储结果：0表示不在集合内，1表示在集合内int tempRN;/ 当前结果int wN;/ 重量int vN;/ 价值int tempV = 0;/ 当前价值int maxV = 0 ;/最大价值int tempW = 0 ;/当前的容量void traceBack( int i )if (i>=N)if (tempV>maxV)maxV = tempV;int j = 0;for (j=0;j<N;j+)result。 = tempRj;return ;
11、/边界情况考虑if (tempW+wi<=C)(tempRi = 1;tempV+=vi; /当前价值增加tempW+=wi ; /当前重量增加traceBack(i+1); / 进入下一层 tempV-=vi ;/当前价值增加tempW-=wi ; /当前重量增加 /左子树/直接进入右子树int k=0;int cp = 0;for (k=i+1;k<N;k+)(cp+= vk;if (tempV+cp>maxV)tempRi = 0;/当前值舍弃traceBack(i+1);void pack()int i=0;printf("请输入各个物品重量和价值(成对输入
12、，例如“79 83 ”)n");for (i=0;i<N;i+)/printf(" 请输入昨物品的重量：t”,i);/ scanf("%d”,&wi);scanf( "%d %d”,&wi,&vi);/*for(i=0;i<N;i+)printf(" 请输入昨物品的价值:t",i);scanf("%d”,&vi);*/traceBack(0);printf("最大价值为 %dt" ,maxV);printf( "n取值情况为n");for (i=0;i<N;i+)printf( "%dt” ,resulti);printf( "n" );for (i=0;i<N;i+)printf( "%dt” ,wi); printf( "n" );for (i=0;i<N;i+)(printf( "%dt” ,vi);)printf( "n");) /背包问题的调用