回溯法求01背包问题.doc

《回溯法求01背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验题目给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包中物品的总价值最大?实验目的（1）掌握回溯法的设计思想；（2）掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；（3）考察回溯法求解问题的有效程度。实验内容（包括代码和对应的执行结果截图）#includeusingnamespacestd;intn,c,bestp;//物品的个数，背包的容量，最大价值intp[100],w[100],x[100],bestx[100];//物品的价

2、值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况voidBacktrack(inti,intcp,intcw)//cw当前包内物品重量，cp当前包内物品价值{intj;if(i>n)//结束回溯{if(cp>bestp){bestp=cp;for(i=0;i<=n;i++)bestx[i]=x[i];}}elsefor(j=0;j<=1;j++){x[i]=j;if(cw+x[i]*w[i]<=c){cw+=w[i]*x[i];//每个解向量的分量的c与当前的w[i]和前一个解向量分量的cw有关cp+=p[i]*x[i];Backtrack

3、(i+1,cp,cw);//递归调用}}}intmain(){inti;bestp=0;cout<<"输入物品个数:"<>n;cout<<"输入背包最大容量:"<>c;cout<<"依次输入物品的重量:"<>w[i];cout<<"请依次输入物品的价值:"<>p[i];Backtrack(1,0,0);cout<<"最大价值为:"<

4、0表示没有被选中，1表示被选中）"<

5、元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即x1=a12。依此类推，一般情况下，如果X=(x1,x2,…,xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：（1）如果X=(x1,x2,…,xi＋1)是问题的最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解；（2）如果X=(x1,x2,…,xi＋1)是问题的部分解，则继续构造解向量的下一个分量；（3）如果X=(x1,x2,…,xi＋1)既不是问题的部分解也不是问题的最终解，则存在下面两种情

6、况：①如果xi+1=ai＋1k不是集合Si＋1的最后一个元素，则令xi+1=ai＋1k＋1，即选择Si+1的下一个元素作为解向量X的第i+1个分量；②如果xi+1=ai＋1k是集合Si＋1的最后一个元素，就回溯到X=(x1,x2,…,xi)，选择Si的下一个元素作为解向量X的第i个分量，假设xi=aik，如果aik不是集合Si的最后一个元素，则令xi=aik＋1；否则，就继续回溯到X=(x1,x2,…,xi－1)；对于n=4的0/1背包问题，其解空间树如图8.2所示，树中的16个叶子结点分别代表该问题的16个可能解。对于n=4的0/1背包问题，三个物

7、品的重量为{7,3,4,5}，价值为{42,12,40,25}，背包容量为10，从图8.2所示的解空间树的根结点开始搜索，搜索过程如下：