[汇总]蛮力法、动态规划法、回溯法和分支限界法求解01背包问题一、实验内容:分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。

C注:0/1背包问题:给定种物品和一个容量为的背包，物品的重量ni是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背wvii 包中的物品的总价值最大。

其中，每种物品只有全部装入背包或不装入背包两种选择。

二、所用算法的基本思想及复杂度分析:1.蛮力法求解0/1背包问题:1)基本思想:对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。

在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。

2)代码:#include<iostream>#include<algorithm>using namespace std;#define N 100 //最多可能物体数 struct goods //物品结构体{int sign; //物品序号int w; //物品重量int p; //物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w); }int max(int a,int b){return a<b?b:a;}int n,C,bestP=0,cp=0,cw=0;int X[N],cx[N];/*蛮力法求解0/1背包问题*/int Force(int i){if(i>n-1){if(bestP<cp&&cw+a[i].w<=C){for (int k=0;k<n;k++) X[k]=cx[k];//存储最优路径bestP=cp;}return bestP;}cw=cw+a[i].w;cp=cp+a[i].p;cx[i]=1; //装入背包Force(i+1);cw=cw-a[i].w;cp=cp-a[i].p;cx[i]=0; //不装入背包Force(i+1);return bestP;}int KnapSack1(int n,goods a[],int C,int x[]) { Force(0);return bestP;}int main(){goods b[N];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].p);b[i]=a[i];}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);bestP=0,cp=0,cw=0;//恢复初始化}3)复杂度分析:n蛮力法求解0/1背包问题的时间复杂度为:。

T(n),O(2)2.动态规划法求解0/1背包问题:1)基本思想:令表示在前个物品中能够装入容量为的V(i,j)i(1,i,n)j(1,j,C)背包中的物品的最大值，则可以得到如下动态函数:V(i,0),V(0,j),0V(i,1,j)(j,w),i V(i,j),,,,VijVijwvjwmax(,1,),(,1,,)，(,)iii, 按照下述方法来划分阶段:第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值;第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值;以此类推，直到第个n C阶段。

最后，便是在容量为的背包中装入个物品时取得的最nV(n,C) 大价值。

2)代码:#include<iostream>#include<algorithm>using namespace std;#define N 100 //最多可能物体数struct goods //物品结构体{int sign; //物品序号int w; //物品重量int p; //物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w);}int max(int a,int b){return a<b?b:a;}int n,C,bestP=0,cp=0,cw=0;int X[N],cx[N];int KnapSack2(int n,goods a[],int C,int x[]) {int V[N][10*N];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];elseV[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p); 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(){goods b[N];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].p);b[i]=a[i];}int sum2=KnapSack2(n,a,C,X);//调用动态规划法求0/1背包问题printf("动态规划法求解0/1背包问题:\nX=[ ");for(i=0;i<n;i++)cout<<X[i]<<" ";//输出所求X[n]矩阵printf("] 装入总价值%d\n",sum2);for (i=0;i<n;i++){a[i]=b[i];}//恢复a[N]顺序}3)复杂度分析:动态规划法求解0/1背包问题的时间复杂度为:。

T(n),O(n，C)3.回溯法求解0/1背包问题:1)基本思想:回溯法:为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。

这种具有限界函数的深度优先生成法称为回溯法。

对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1可用子集数表示。

在搜索解空间树时，只要其左儿子结点是一向量组成, 个可行结点，搜索就进入左子树。

当右子树中有可能包含最优解时就进入右子树搜索。

2)代码:#include<iostream>#include<algorithm>using namespace std;#define N 100 //最多可能物体数struct goods //物品结构体{int sign; //物品序号int w; //物品重量int p; //物品价值}a[N];bool m(goods a,goods b){return (a.p/a.w)>(b.p/b.w);}int max(int a,int b){return a<b?b:a;}int n,C,bestP=0,cp=0,cw=0;int X[N],cx[N];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].p;cx[a[i].sign]=1; //装入背包BackTrack(i+1);cw=cw-a[i].w;cp=cp-a[i].p; //回溯，进入右子树}cx[a[i].sign]=0; //不装入背包BackTrack(i+1);return bestP;}int KnapSack3(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;}int main(){goods b[N];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].p);b[i]=a[i];}int sum3=KnapSack3(n,a,C,X);//调用回溯法求0/1背包问题printf("回溯法求解0/1背包问题:\nX=[ ");for(i=0;i<n;i++)cout<<X[i]<<" ";//输出所求X[n]矩阵printf("] 装入总价值%d\n",sum3);for (i=0;i<n;i++){a[i]=b[i];}//恢复a[N]顺序3)复杂度分析:最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为:n。