回溯法的应用01背包等问题

1、精选优质文档-倾情为你奉上实验4. 回溯法的应用- 0-1背包等问题实验内容本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试），通过回溯法的在实际问题求解实践中，加深理解其基本原理和思想以及求解步骤。求解的问题为0-1背包。作为挑战：可以考虑回溯法在其他问题（如最大团问题、旅行商、图的m着色问题）。实验目的u 理解回溯法的核心思想以及求解过程（确定解的形式及解空间组织，分析出搜索过程中的剪枝函数即约束函数与限界函数）；u 掌握对几种解空间树（子集树、排列数、满m叉树）的回溯方法；u 从算法分析与设计的角度，对0-1背包问题

2、的基于回溯法求解有更进一步的理解。环境要求对于环境没有特别要求。对于算法实现，可以自由选择C, C+, Java，甚至于其他程序设计语言。实验步骤0-1背包;步骤1：n个物品和1个背包。对物品i，其价值为vi，重量为wi，背包容量为W。如何选取物品装入背包，使背包中所装入的物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品。约束条件：目标函数：步骤2：（1）物品有n种，背包容量为C，分别用pi和wi存储第i种物品的价值和重量，用xi标记第i种物品是否装入背包，用bestxi存储第i种物品的最优装载方案；（2

3、）用递归函数Backtrack (i,cp,cw)来实现回溯法搜索子集树（形式参数i表示递归深度，n用来控制递归深度，形式参数cp和cw表示当前总价值和总重量，bestp表示当前最优总价值）： 若i >n，则算法搜索到一个叶结点，判断当前总价值是否最优：1> 若cp>bestp，更新当前最优总价值为当前总价值（即bestp=cp），更新装载方案（即bestxi=xi( 1in)）； 采用for循环对物品i装与不装两种情况进行讨论（0j1）：l xi=j；l 若总重量不大于背包容量（即cw+xi*wi<=c），则更新当前总价 br=""> 值和总

4、重量（即cw+=wi*xi,cp+=pi*xi）, 对物品i+1调用递归函数Backtrack(i+1,cp,cw) 继续进行装载；l 函数Backtrack(i+1,cp,cw)调用结束后则返回当前总价值和总重量（即 cw-=wi*xi,cp-=pi*xi）；l 当j>1时，for循环结束； 当i=1时，若已测试完所有装载方案，外层调用就全部结束；（3）主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程，最终得到的bestp和bestxi即为所求最大总价值和最优装载方案。 步骤3：BACKTRACK-KNAPSACK-01-REC(t,w,v,W) if t >

5、; n /到达叶子结点 /如果找到多个解，那就择优 OUTPUT(x) /x1.n: 为问题的解，xi取值0或1 bestp = cp return if cw + wt <= W /搜索左子树 xt=1 /x1.n: 为解向量，xi取值0或1 cw += wt /当前背包中物品的总重量 cp += vt /当前背包中物品的总价值 BACKTRACK-KNAPSACK-01-REC(t+1,w,v,W); cw -= wt cp -= vt if BOUND(t+1,W-cw,cp,w,v) > bestp /搜索右子树 xt=0 BACKTRACK-KNAPSACK-01-REC

6、(t+1,w,v,W)计算上界：BOUND(i,cRemained,cp,w,v) /i为第i层。 /cRemained为背包的剩余容量，cp为当前背包中物品的总价值 b = cp while i <= n && wi <= cRemained cRemained -= wi b += vi i + /装满背包if i <= n b += vi / wi * cRemainedreturn b /cp+brp步骤4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明（这里可以略去。有兴趣可以深入一下“多米诺性质”）；步骤5：时间复杂度：O(2

7、n) + O(n2n) = O(n2n)。步骤6：#include<stdio.h>int n,c,bestp;/物品的个数，背包的容量，最大价值int p10000,w10000,x10000,bestx10000;/物品的价值，物品的重量，xi暂存物品的选中情况,物品的选中情况void Backtrack(int i,int cp,int cw) /cw当前包内物品重量，cp当前包内物品价值 int j; if(i>n)/回溯结束 if(cp>bestp) bestp=cp; for(i=0;i<=n;i+) bestxi=xi; else for(j=0;j

8、<=1;j+) xi=j; if(cw+xi*wi<=c) cw+=wi*xi; cp+=pi*xi; Backtrack(i+1,cp,cw); cw-=wi*xi; cp-=pi*xi; int main() int i; bestp=0; printf("请输入背包最大容量:n"); scanf("%d",&c); printf("请输入物品个数:n"); scanf("%d",&n); printf("请依次输入物品的重量:n"); for(i=1;i<

9、=n;i+) scanf("%d",&wi); printf("请依次输入物品的价值:n"); for(i=1;i<=n;i+) scanf("%d",&pi); Backtrack(1,0,0); printf("最大价值为:n"); printf("%dn",bestp); printf("被选中的物品依次是(0表示未选中，1表示选中)n"); for(i=1;i<=n;i+) printf("%d ",bestxi); printf("n"); return 0;实验总结通过这次实验，我发现自己实验过程中有很多问题，算法的复杂性分析也存在一定的问题。通过上网查询了解了回溯法，回溯法虽然是通过搜索问题的解空间来得