回溯法求背包问题

1、算法设计与分析实验报告学 号： 姓 名： 日 期： 得 分： 一、实验内容：用回溯法求解0/1背包问题注：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。二、所用算法的基本思想及复杂度分析：1.回溯法求解背包问题：1） 基本思想：回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/

2、1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。2）复杂度分析：回溯法求解0/1背包问题的时间复杂度为：。空间复杂度：有个物品，即最多递归层，存储物品信息就是一个一维数组，即回溯法求解0/1背包问题的空间复杂度为。2.以动态规划法验证：1）基本思想：令表示在前个物品中能够装入容量为的背包中的物品的最大值，则可以得到如下动态函数：按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的

3、背包能够得到的最大价值；以此类推，直到第个阶段。最后，便是在容量为的背包中装入个物品时取得的最大价值。2）复杂度分析：动态规划法求解0/1背包问题的时间复杂度为：。三、源程序及注释：#include<iostream>#include<algorithm>using namespace std;struct goods/物品结构体int sign;/物品序号int w;/物品重量int v;/物品价值a100;bool m(goods a,goods b)return (a.v/a.w)>(b.v/b.w);int max(int a,int b)return a

4、<b?b:a;int n,C,bestP=0,cp=0,cw=0;int x100,cx100;/回溯法函数int BackTrack(int i)if(i>n-1)if(bestP<cp)for (int k=0;k<n;k+)xk=cxk;/存储最优路径bestP=cp;return bestP;if(cw+ai.w<=C)/进入左子树cw=cw+ai.w;cp=cp+ai.v;cxai.sign=1;/装入背包BackTrack(i+1);cw=cw-ai.w;cp=cp-ai.v;/回溯，进入右子树cxai.sign=0;/不装入背包BackTrack(i

5、+1);return bestP;/回溯法求解0/1背包问题int KnapSack(int n,goods a,int C,int x)for(int i=0;i<n;i+)xi=0;ai.sign=i;sort(a,a+n,m);/将各物品按单位重量价值降序排列BackTrack(0);return bestP;/动态规划法求解0/1背包问题int KnapSack1(int n,goods a,int C,int x)int V1001000;for(int i=0;i<=n;i+)/初始化第0列Vi0=0;for(int j=0;j<=C;j+)/初始化第0行V0j=

6、0;for(i=1;i<=n;i+)/计算第i行，进行第i次迭代for(j=1;j<=C;j+)if(j<ai-1.w)Vij=Vi-1j;elseVij=max(Vi-1j,Vi-1j-ai-1.w+ai-1.v);j=C;/求装入背包的物品for (i=n;i>0;i-)if (Vij>Vi-1j)xi-1=1;j=j-ai-1.w;elsexi-1=0;return VnC;/返回背包取得的最大价值/测试以上算法的主函数int main()printf("物品种数n: ");scanf("%d",&n);/输入

7、物品种数printf("背包容量C: ");scanf("%d",&C);/输入背包容量for (int i=0;i<n;i+)/输入物品i的重量w及其价值vprintf("物品%d的重量w%d及其价值v%d: ",i+1,i+1,i+1);scanf("%d%d",&ai.w,&ai.v);int sum1=KnapSack1(n,a,C,x);/调用动态规划法求0/1背包问题printf("动态规划法求解0/1背包问题:nX= ");for(i=0;i<n

8、;i+)cout<<xi<<" "/输出所求Xn矩阵printf("装入总价值%dn",sum1);int sum2=KnapSack(n,a,C,x);printf("回溯法求解0/1背包问题:nX= ");for(i=0;i<n;i+)cout<<xi<<" "/输出所求Xn矩阵printf("装入总价值%dn",sum2);return 0;四、运行输出结果：相同的数据，求相同同的问题，用不同的方法，得到的结果，所得结果正是所求问题的最优解，以动态规划法验证回溯法求解的0/1背包问题是正确的。五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：1.本实验中用回溯法求0/1背包问题，课本上给出的算法伪代码只能求出背包装入物品的最大总价值，所以我在对物品构造结构体时定义了一个int型变量sign，用来记录所给物品的原始顺序，并在适当位置记录装入和不装入背包，存储求解路径，从而求出原始问题的解向量X。2.在本实验中，本为增强回溯法求解0/1背包问题函数的可移植性，只定义局部变量而不定义