回溯法求01背包问题

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

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

2、100],bestx[l00];//物品的价值，物品的重量，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<=l;j++)x[i]=j;if(cw+x[i]*w[i]<=c)cw+=w[i]*x[i];//每个解向量的分量的c与当

3、前的w[i]和前一个解向量分量的cw有关cp+=pfil*xfil;Backtrack(i+1，cp，cw);//递归调用}}}intmain(){inti;bestp=O;cout«”输入物品个数:”《endl;cin»n;cout«"输入背包最大容量:”《endl;cin»c;cout«’’依次输入物品的重量:n«endl;for(i=l;i<=n;i++)cin»wfi];cout«"请依次输入物品的价值:"《endl;for(i=l;i<=n;i++)cin»p[i];Backtrack(1,0,

4、0);cout«n最大价值为:H«endl«bestp«endl;cout«”物品的选中情况依次为(0表示没冇被选中，1表示被选中)n«endl;for(i=l;i<=n;i++)cout«bestx[i];cout«endl;return0;实验结果分析由于问题的解向量X=（xl,a2,A77）中的每个分量彡71）都展于一个有限集合如｛以1，以2，...，以叫，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积SIxS2X...XSA2中的元素。初始时，令解向量X为空，然后，从根结点出发，选择S1

5、的第一个元素作为解向量X的第一个分量，即Xl=6/ll,如果X=(X1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即xl=al2.依此类推，一般情况下，如果X=(;d，x2，...，功是问题的部分解，则选择A+1的第一个元素作为解向量X的第个分量时，有下面三种情况：(1)如果X=(xl，x2,...，x/+1)是问题的最终解，则输出这个解。如果问题只希望得到一个解，则结朿搜索，否则继续搜索其他解；(2)如果X=(x

6、l，x2,...，h+1)是问题的部分解，则继续构造解向量的下一个分量；(3)如果X=(xl，x2,...，xf+l慨不是问题的部分解也不是问题的最终解,则存在下面两种情况：①如果tn'+R不是集合57+1的最后一个元素，则令xZ+l=ai+lk+1,即选择S/+1的下一个元素作为解向量X的第f+1个分量；②如果％/+l=fzZ+U是集合A+1的最后一个元素，就回溯到X=(xl，x2，...，xZ),选择57的下一个元素作力解向量X的第/个分量，假设x/=6zz7:，如果6/认不是集合57的最后一个元素，

7、贝IJ令xZ=aZA+l;否则，就继续回溯到X=(xl，x2,...，xZ—1)；对于n=4的0/1背包问题，其解空间树如图8.2所示，树中的16个叶子结点分别代表该问题的16个可能解。0^，\1对物品1的选择’>4-一--一0/10//J对物品2的选孫/V7v'°/1°/i0/1xmil湖迭择Cj）⑻（14^1G）（会）'26）（29）八"A1☆"A1驅醐对于n=4的0/1背包问题，三个物品的重量为｛7,3,4,5｝,价值为｛42,12,40,25｝，背包容量为10,从图8.2所示的解空间

8、树的根结点开始搜索，搜索过程如下：対物品2的选楛对物品3的选择对物品4的选襌