回溯法求01背包问题(共6页)

1、精选优质文档-倾情为你奉上实验题目给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包中物品的总价值最大?实验目的（1）掌握回溯法的设计思想；（2）掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；（3）考察回溯法求解问题的有效程度。实验内容（包括代码和对应的执行结果截图）#include<iostream>using namespace std;int n,c,bestp; /物品的个数，背包的容量，最大价值int p100,w100,x100,bestx100; /物品的价值，物品的重量

2、，xi暂存物品的选中情况,物品的选中情况void Backtrack(int i,int cp,int cw) /cw当前包内物品重量，cp当前包内物品价值 int j; if(i>n)/结束回溯 if(cp>bestp) bestp=cp; for(i=0;i<=n;i+) bestxi=xi; else for(j=0;j<=1;j+) xi=j; if(cw+xi*wi<=c) cw+=wi*xi; /每个解向量的分量的c与当前的wi和前一个解向量分量的cw有关 cp+=pi*xi;Backtrack(i+1,cp,cw); /递归调用 int main()

3、 int i; bestp=0;cout<<"输入物品个数:"<<endl;cin>>n;cout<<"输入背包最大容量:"<<endl;cin>>c;cout<<"依次输入物品的重量:"<<endl; for(i=1;i<=n;i+) cin>>wi;cout<<"请依次输入物品的价值:"<<endl; for(i=1;i<=n;i+) cin>>pi; Ba

4、cktrack(1,0,0);cout<<"最大价值为:"<<endl<<bestp<<endl;cout<<"物品的选中情况依次为（0表示没有被选中，1表示被选中）"<<endl; for(i=1;i<=n;i+) cout<<bestxi; cout<<endl; return 0; 实验结果分析由于问题的解向量X=(x1, x2, , xn)中的每个分量xi(1in)都属于一个有限集合Si=ai1, ai2, , airi，因此，回溯法可以按某种顺

5、序（例如字典序）依次考察笛卡儿积S1×S2××Sn中的元素。 初始时，令解向量X为空，然后，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1= a11，如果X=(x1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即x1= a12。依此类推，一般情况下，如果X=(x1, x2, , xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：（1）如果X=(x1, x2, , xi1)是问题的最终解，则输出这个解。如果问题只

6、希望得到一个解，则结束搜索，否则继续搜索其他解；（2）如果X=(x1, x2, , xi1)是问题的部分解，则继续构造解向量的下一个分量；（3）如果X=(x1, x2, , xi1)既不是问题的部分解也不是问题的最终解，则存在下面两种情况： 如果xi+1= ai1k不是集合Si1的最后一个元素，则令xi+1= ai1k1，即选择Si+1的下一个元素作为解向量X的第i+1个分量； 如果xi+1= ai1k是集合Si1的最后一个元素，就回溯到X=(x1, x2, , xi)，选择Si的下一个元素作为解向量X的第i个分量，假设xi= aik，如果aik不是集合Si的最后一个元素，则令xi= aik1；否则，就继续回溯到X=(x1, x2, , xi1)；对于n=4的0/1背包问题，其解空间树如图8.2所示，树中的16个叶子结点分别代表该问题的16个可