当前位置:首页 >> 计算机软件及应用 >>

回溯法求0-1背包问题


《算法设计与分析》实验报告
学 日 号: 期: 姓 得 名: 分:

一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi ,其价值为

vi ,背包问题是如何使选择装入背包内的物品,使得装入背包中的物品的总
价值最大。其中,每种物品只有全部装入背包或不装入背包两种选择。 二、所用算法的基本思想及复杂度分析: 1.回溯法求解背包问题: 1)基本思想: 回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断 地利用限界函数(bounding function)来处死那些实际上不可能产生所 需解的活结点,以减少问题的计算量。这种具有限界函数的深度优先生 成法称为回溯法。 对于有 n 种可选物品的 0/1 背包问题,其解空间由长度为 n 的 0-1 向量组成,可用子集数表示。在搜索解空间树时,只要其左儿子结点是一 个可行结点,搜索就进入左子树。当右子树中有可能包含最优解时就进 入右子树搜索。 2)复杂度分析: 回溯法求解 0/1 背包问题的时间复杂度为: T (n) ? O(2n ) 。 空间复杂度:有 n 个物品,即最多递归 n 层,存储物品信息就是一个 一维数组,即回溯法求解 0/1 背包问题的空间复杂度为 O (n) 。 2.以动态规划法验证: 1)基本思想: 令 V (i, j ) 表示在前 i(1 ? i ? n) 个物品中能够装入容量为 j (1 ? j ? C ) 的 背包中的物品的最大值,则可以得到如下动态函数:
V (i,0) ? V (0, j ) ? 0

?V (i ? 1, j )( j ? wi ) V (i, j ) ? ? V ?max? (i ? 1, j ),V (i ? 1, j ? wi ) ? vi ?( j ? wi )
按照下述方法来划分阶段:第一阶段,只装入前 1 个物品,确定在 各种情况下的背包能够得到的最大价值;第二阶段,只装入前 2 个物品,
1

确定在各种情况下的背包能够得到的最大价值;以此类推,直到第 n 个 阶段。最后, V (n, C ) 便是在容量为 C 的背包中装入 n 个物品时取得的最 大价值。 2)复杂度分析: 动态规划法求解 0/1 背包问题的时间复杂度为: T (n) ? O(n ? C ) 。 三、源程序及注释:
#include<iostream> #include<algorithm> using namespace std; struct goods //物品结构体 { int sign; //物品序号 int w; //物品重量 int v; //物品价值 }a[100]; bool m(goods a,goods b) { return (a.v/a.w)>(b.v/b.w); } int max(int a,int b) { return a<b?b:a; } int n,C,bestP=0,cp=0,cw=0; int x[100],cx[100]; //回溯法函数 int BackTrack(int i) { if(i>n-1){ if(bestP<cp){ for (int k=0;k<n;k++) x[k]=cx[k];//存储最优路径 bestP=cp; } return bestP; } if(cw+a[i].w<=C){ //进入左子树 cw=cw+a[i].w; cp=cp+a[i].v; cx[a[i].sign]=1; //装入背包 BackTrack(i+1); cw=cw-a[i].w; cp=cp-a[i].v; //回溯,进入右子树
2

} cx[a[i].sign]=0; BackTrack(i+1); return bestP;

//不装入背包

} //回溯法求解 0/1 背包问题 int KnapSack(int n,goods a[],int C,int x[]) { for(int i=0;i<n;i++) { x[i]=0; a[i].sign=i; } sort(a,a+n,m);//将各物品按单位重量价值降序排列 BackTrack(0); return bestP; } //动态规划法求解 0/1 背包问题 int KnapSack1(int n,goods a[],int C,int x[]) { int V[100][1000]; for(int i=0;i<=n;i++) //初始化第 0 列 V[i][0]=0; for(int j=0;j<=C;j++) //初始化第 0 行 V[0][j]=0; for(i=1;i<=n;i++) //计算第 i 行,进行第 i 次迭代 for(j=1;j<=C;j++) if(j<a[i-1].w) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].v); j=C; //求装入背包的物品 for (i=n;i>0;i--) { if (V[i][j]>V[i-1][j]){ x[i-1]=1; j=j-a[i-1].w; } else x[i-1]=0; } return V[n][C]; //返回背包取得的最大价值 } //测试以上算法的主函数 int main()

3

{ printf("物品种数 n: "); scanf("%d",&n); //输入物品种数 printf("背包容量 C: "); scanf("%d",&C); //输入背包容量 for (int i=0;i<n;i++) //输入物品 i 的重量 w 及其价值 v { printf("物品%d 的重量 w[%d]及其价值 v[%d]: ",i+1,i+1,i+1); scanf("%d%d",&a[i].w,&a[i].v); } int sum1=KnapSack1(n,a,C,x);//调用动态规划法求 0/1 背包问题 printf("动态规划法求解 0/1 背包问题:\nX=[ "); for(i=0;i<n;i++) cout<<x[i]<<" ";//输出所求 X[n]矩阵 printf("] 装入总价值%d\n",sum1); int sum2=KnapSack(n,a,C,x); printf("回溯法求解 0/1 背包问题:\nX=[ "); for(i=0;i<n;i++) cout<<x[i]<<" ";//输出所求 X[n]矩阵 printf("] 装入总价值%d\n",sum2); return 0; }

四、运行输出结果:

相同的数据,求相同同的问题,用不同的方法,得到的结果,所得结果 正是所求问题的最优解,以动态规划法验证回溯法求解的 0/1 背包问题是正 确的。 五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训: 1.本实验中用回溯法求 0/1 背包问题,课本上给出的算法伪代码只能求出背 包装入物品的最大总价值, 所以我在对物品构造结构体时定义了一个 int 型变量 sign,用来记录所给物品的原始顺序,并在适当位置记录装入和不装入背包,存 储求解路径,从而求出原始问题的解向量 X。 2.在本实验中,本为增强回溯法求解 0/1 背包问题函数的可移植性,只定义 局部变量而不定义全局变量, 花费大量时间不断改进调试都未能达到目的,走了 各种弯路, 最终总是因为函数之间参数无法传递导致运行错误。这让我真正意识
4

到了自己在参数传递、 指针变量方面知识的掌握不太牢固,同时认识到了定义全 局变量的一些好处,以后尽量不要片面追求所编函数的可移植性而拒用全局变 量,以此为戒。

5


相关文章:
用回溯法解决0-1背包问题
标签: 回溯法| 背包| 用回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决0-1背包问题 #include&lt;stdio.h&gt; int c; //背包容量 ...
回溯算法解决0-1背包问题
回溯算法解决0-1背包问题 - 《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称:回溯算法....
回溯法解0-1背包问题实验报告
实验4 一 、实验要求 回溯法0-1 背包问题 1.要求用回溯法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。 ...
回溯算法解决0-1背包问题(DOC)
回溯算法解决0-1背包问题(DOC) - 《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: 信息工程学院 实验项目名称...
回溯法-0-1背包问题
回溯法-0-1背包问题 - 1、 问题描述 一、0-1 背包问题 给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,如何选择才能使 得物品的总价格最高...
0-1背包问题的解决(回溯法)
回溯法| 背包| 0-1背包问题的解决(回溯法)_解决方案_计划/解决方案_实用文档。算法设计分析,通过回溯法和动态规划的方法解决0-1背包问题。 前面...
解0-1背包问题的动态规划算法
0/1背包问题是工程问题的典型概括,怎么样高效求出最优决策,是人们关心 的问题...(5)若不满足循环次数转(3),否则转(6);(6)用回溯法确定决策序列;终止程序...
0-1背包问题(回溯法)
0-1背包问题(回溯法) - 0-1 背包问题(回溯法) 实验报告 姓 名: 学 号: 指导老师: 一.算法设计名称: 0-1 背包问题(回溯法) 二.实验内容 问题描述: ...
回溯法解决01背包问题
回溯法解决01背包问题 - 回溯法个既带有系统性又带有跳跃性的搜索算法。 它在包含问题的所有解的解空间树中按照 深度优先的策略,从根节点出发搜索解空间树。...
回溯法和分支限界法解决0-1背包题(精)
0-1 背包问题 计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一 个(...
更多相关标签: