回溯法求0-1背包问题
- 格式：doc
- 大小：116.50 KB
- 文档页数：5
1 《算法设计与分析》实验报告
学 号： 姓 名：
日 期： 得 分：
一、实验内容：
用回溯法求解0/1背包问题
注：给定n种物品和一个容量为C的背包，物品i的重量是iw，其价值为iv，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。
二、所用算法的基本思想及复杂度分析：
1.回溯法求解背包问题：
1）基本思想：
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。
对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。
2）复杂度分析：
回溯法求解0/1背包问题的时间复杂度为：)2()(nOnT。
空间复杂度：有n个物品，即最多递归n层，存储物品信息就是一个一维数组，即回溯法求解0/1背包问题的空间复杂度为)(nO。
2.以动态规划法验证：
1）基本思想：
令),(jiV表示在前)1(nii个物品中能够装入容量为)1(Cjj的背包中的物品的最大值，则可以得到如下动态函数：
0),0()0,(jViV
)(),1(),,1(max))(,1(),(iiiiwjvwjiVjiVwjjiVjiV
按照下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品， 2 确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个阶段。最后，),(CnV便是在容量为C的背包中装入n个物品时取得的最大价值。
2）复杂度分析：
动态规划法求解0/1背包问题的时间复杂度为：)()(CnOnT。
三、源程序及注释：
#include
#include
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 } int n,C,bestP=0,cp=0,cw=0; int x[100],cx[100]; //回溯法函数 int BackTrack(int i) { if(i>n-1){ if(bestP for (int k=0;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; //回溯，进入右子树 3 } 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 { 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 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() 4 { printf("物品种数n: "); scanf("%d",&n); //输入物品种数 printf("背包容量C: "); scanf("%d",&C); //输入背包容量 for (int i=0;i { 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 cout< printf("] 装入总价值%d\n",sum1); int sum2=KnapSack(n,a,C,x); printf("回溯法求解0/1背包问题:\nX=[ "); for(i=0;i cout< printf("] 装入总价值%d\n",sum2); return 0; } 四、运行输出结果： 相同的数据，求相同同的问题，用不同的方法，得到的结果，所得结果正是所求问题的最优解，以动态规划法验证回溯法求解的0/1背包问题是正确的。 五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训： 1.本实验中用回溯法求0/1背包问题，课本上给出的算法伪代码只能求出背包装入物品的最大总价值，所以我在对物品构造结构体时定义了一个int型变量sign，用来记录所给物品的原始顺序，并在适当位置记录装入和不装入背包，存储求解路径，从而求出原始问题的解向量X。 2.在本实验中，本为增强回溯法求解0/1背包问题函数的可移植性，只定义局部变量而不定义全局变量，花费大量时间不断改进调试都未能达到目的，走了各种弯路，最终总是因为函数之间参数无法传递导致运行错误。这让我真正意识 5 到了自己在参数传递、指针变量方面知识的掌握不太牢固，同时认识到了定义全局变量的一些好处，以后尽量不要片面追求所编函数的可移植性而拒用全局变量，以此为戒。
