(完整word版)0-1背包问题四种不同算法的实现.

1、兰州交通大学数理与软件工程学院题目 0-1 背包问题算法实现院系数理院专业班级信计 09学生姓名雷雪艳学号200905130指导教师李秦二一二年六月五日一、问题描述：1、01 背包问题：给定n 种物品和一个背包，背包最大容量为M ，物品 i 的重量是 wi ,其价值是平 Pi，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大？背包问题的数学描述如下：2、要求找到一个 n 元向量 (x1，x2xn)，在满足约束条件：xi wiMmaxxi pi0 xi1 情况下，使得目标函数，其中，1 i n；M>0 ；wi>0 ；pi>0 。满足约束条件的任何向量都是一个可行解，

2、而使得目标函数达到最大的那个可行解则为最优解1 。给定 n种物品和 1 个背包。物品 i的重量是 wi ，其价值为 pi ，背包的容量为 M 。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i 只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次，也不能只装入部分的物品i。该问题称为 0-1 背包问题。0-1 背包问题的符号化表示是，给定M>0， w i >0 ， pi >0， 1in ，要求找到一个 n 元 0-1 向量向量 (x1， x2xn)， X i =0 或 1 , 1 in,使得xi wi Mxi pi，而

3、且达到最大 2 。二、解决方案：方案一：贪心算法1、贪心算法的基本原理与分析贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑， 它所作出的选择只是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解， 但对范围相当广的许多问题它能产生整体最优解。 在一些情况下， 即使贪心算法不能得到整体最优解， 但其最终结果却是最优解的很好近似解。贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的

4、主要区别。 当一个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质。 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。2、0-1 背包问题的实现对于 0-1 背包问题，设 A 是能装入容量为 c 的背包的具有最大价值的物品集合，则 Aj=A-j 是 n-1 个物品 1,2,.,j-1,j+1,.,n 可装入容量为 c-wj 的背包的具有最大价值的物品集合。用贪心算法求解0-1 背包问题的步骤是，首先计算每种物品单位重量的价值 vi/wi ；然后，将物品进行排序，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的

5、物品总量未超过 c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去，直到背包装满为止。3、算法设计如下：#include<iostream.h>float#definemax100vmax,wmax,totalv=0,totalw=0/最多物品数,limitw;void sort (int n,float amax,floatcout<<"请输入 n 和 limitw:"bmax)/按价值密度排序cin>>n >>limitw;for(i=1;i<=n;i+)int j,h,k;xi=0;floa

6、t t1,t2,t3,cmax;/物品选择情况表初始化为 0for(k=0;k<n;k+)cout<<"请依次输入物品的价值：ck=ak/bk;"<<endl;for(j=0;j<n;j+)for(i=1;i<=n;i+)if(cj<cj+1)cin>>vi;t1=aj;aj=aj+1;aj+1=t1;cout<<endl;t2=bj;bj=bj+1;bj+1=t2;cout<<"请依次输入物品的重量：t3=cj;cj=cj+1;cj+1=t3;"<<endl

7、;for(i=1;i<=n;i+)cin>>wi;voidknapsack(intn,floatcout<<endl;limitw,floatvmax,floatknapsack (n,limitw,v,w,x);wmax,int xmax)cout<<"the selection is:"floatc1;for(i=1;i<=n;i+)/c1 为背包剩余可装载重量int i;cout<<xi;sort(n,v,w);if(xi=1)/物品按价值密度排序totalw=totalw+wi;c1=limitw;tota

8、lv=totalv+vi;for(i=0;i<n;i+)if(wi>c1)break;cout<<endl;xi=1;cout<<" 背 包 的 总 重 量 为 ：/xi 为 1 时，物品 i 在解中"<<totalw<<endl; / 背包所装载c1=c1-wi;总重量cout<<" 背 包 的 总 价 值 为 ："<<totalv<<endl; / 背包的总价值void main()int n,i,xmax;4、贪心算法运行结果如下图所示：方案二：动态规划

9、算法1、动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题， 先求解子问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1 背包问题的主要步骤如下：分析最优解的结

10、构：最有子结构性质；建立递归方程；计算最优值；4构造最优解。2、 0-1 背包问题的实现 最优子结构性质0-1 背包问题具有最优子结构性质。设 (y1， y2yn)是所给 0-1 背包问题的一个最优解，则 (y2，y3yn)是下面相应子问题的一个最优解：nmaxvk xkk i nwk xkjkixk 0,1, ikn因若不然，设 (z2，z3 zn)是上述问题的一个最优解，而(y2，y3yn)不是它nnvi yiw1y1的最优解，由此可见 i 2i 2,且nnv1y1vi zivi yii 2i 1nwi zii 2c。因此nw1y1wi zii2c这说明 (y1， z2zn)是所给0-1

11、背包问题的一个更优解，从而(y1， y2 yn)1 递归关系设所给 0-1 背包问题的子问题nmaxvk xkk inwk xkjkixk 0,1, ikn的最优值为 m(i,j) ，即 m(i,j) 是背包容量为 j，可选择物品为 i，i+1， ， n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子结构性质，可以建立计算 m(i,j) 的递归式如下：maxm(i 1), j ),m(i 1, jwi) vi, j wim(i, j)m(i 1, j ),0 jwjvnjwnm(n, j)wn0 j3、算法设计如下：#include<iostream>#include&

12、lt;iomanip>using namespace std;const int MAX=1000;intwMAX,vMAX,bestMAX;int VMAXMAX;/ 最大价值矩阵int W,n;/W为背包的最大载重量， n 为物品的数量/求最大值函数int max(int x,int y)return x >= y?x:y;/求最小值函数int min(int x,int y)return x>= y ? y:x;void Knaspack()int Max=min(wn-1,W);for(int j=1; j <= Max ; j+)Vnj=0;for(j=wn;

13、 j <= W ; j+)Vnj=vn;for(int i=n-1;i > 1 ; i-)Max=min(wi-1,W);for( j=1; j <= Max ; j+)Vij=Vi+1j;for( j=wi; j <= W; j+)Vij=max(Vi+1j,Vi+1j-wi+vi);V1W=V2W;/先假设第一个物品不放入if(W > w1)for(int i=1;i<=n;i+)cin>>wi;V1W=max(V1W,V2W-w1+v1);/生成向量数组，决定某一个物品是否应该放入背包void Traceback()for(int i=1;

14、 i < n ; i+) /比较矩阵两邻两行 (除最后一行 )，背包容量为 W 的最优值 .if(ViW= Vi+1W)/如果当前行的最优值与下一行的最优值相等， 则表明该物品不能放入。besti=0;else/否则可以放入besti=1;W-=wi;memset(V,0,sizeof(V);cout<<" 输入每件商品的价值v:"<<endl;for( i=1;i<=n;i+)cin>>vi;Knaspack();/构造矩阵 Traceback(); / 求出解的向量数组int totalW=0;int totalV=0;/

15、显示可以放入的物品cout<<" 所 选 择 的 商 品 如下:"<<endl;cout<<" 序 号 i: 重量 w: 价格 v:"<<endl;for(i=1; i <= n ; i+)if(besti = 1)totalW+=wi;totalV+=vi;cout<<setiosflags(ios:left)<<sebestn=(VnW )?1:0;tw(5)<<i<<""<<wi<<""

16、;<<vi<<endl;void main()cout<<"输入商品数量n 和背cout<<" 放入的物品重量总和包容量 W:"是 :"<<totalW<<"价值最优解cin>>n>>W;是:"<<V1W<<"cout<<"输入每件商品的重量"<<totalV<<endl;w:"<<endl;4、计算复杂性分析利用动态规划求解 0

17、-1 背包问题的复杂度为 0(minnc,2n 。动态规划主要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高效地解决问题8 。5、动态规划运行结果如下图所示：方案三：回溯法1、回溯法的基本原理与分析回溯是一种系统地搜索问题解答的方法。为了实现回溯， 首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的 )。回溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的 )。使用递归回溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解奉但是由于此问题解的总组合数有

18、2 n 个，因此随着物件数n 的增大，其解的空间将以n 2 n 级增长，当 n 大到一定程度上，用此算法解决背包问题将是不现实的。下一步是组织解空间以便它能被容易地搜索。 典型的组织方法是图或树。一旦定义了解空间的组织方法，这个空间即可按照深度优先的方法从开始结点进行搜索，利用限界函数避免移动到不可能产生解的子空间。2、 0-1 背包问题的实现回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解( 可能是最优的 )。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先

19、形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是 r为还未遍历的对象的收益之和，将r 加到 cp (当前节点所获收益 )之上，若 (r+cp)目前最优解的收益)，则不需搜索右子树。一种更有bestp(效的方法是按收益密度vi/wi 对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放人背包的对象时，就使用它的一部分。3、算法设计如下：#inclu

20、de<iostream>w,int c,int n );using namespace std;public:class Knapvoid print()friend int Knapsack(intp,intfor(int m=1;m<=n;m+)cout<<bestxm<<" "cout<<endl;private:int Bound(int i);void Backtrack(int i);int c;/背包容量int n; / 物品数int *w;/ 物品重量数组int *p;/ 物品价值数组int cw;/ 当

21、前重量int cp;/当前价值int bestp;/当前最优值int *bestx;/ 当前最优解int *x;/ 当前解;int Knap:Bound(int i)/计算上界int cleft=c-cw;/ 剩余容量int b=cp;/以物品单位重量价值递减序装入物品while(i<=n&&wi<=cleft)cleft-=wi;b+=pi;i+;/装满背包if(i<=n)b+=pi/wi*cleft;return b;void Knap:Backtrack(int i)if(i>n)if(bestp<cp)for(int j=1;j<=n

22、;j+)bestxj=xj;bestp=cp;return;if(cw+wi<=c) / 搜索左子树xi=1;cw+=wi;cp+=pi;Backtrack(i+1);cw-=wi;cp-=pi;if(Bound(i+1)>bestp)/ 搜索右子树xi=0;Backtrack(i+1);class ObjectfriendintKnapsack(intp,intw,int c,int n);public:int operator<=(Object a)constreturn (d>=a.d);private:int ID;float d;intKnapsack(int

23、 p,intw,intc,int n)/为 Knap:Backtrack 初始化 int W=0;int P=0;int i=1;Object *Q=new Objectn;for(i=1;i<=n;i+)Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W<=c)return P;/装入所有物品/依物品单位重量排序float f;for( i=0;i<n;i+)for(int j=i;j<n;j+)if(Qi.d<Qj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;Knap K;K.p = new intn+1;K.w =

24、 new intn+1;K.x = new intn+1;K.bestx = new intn+1;K.x0=0;K.bestx0=0;for( i=1;i<=n;i+)return K.bestp;void main()int *p;int *w;int c=0;int n=0;int i=0;char k;while(k)cout<<" 请 输入背包 容量 (c) ："<<endl;cin>>c;cout<<"请输入物品的个数(n)："<<endl;cin>>n;p=new

25、 intn+1;w=new intn+1;p0=0;w0=0;cout<<"请输入物品的价值(p)："<<endl;for(i=1;i<=n;i+)cin>>pi;cout<<"请输入物品的重量(w) ：K.pi=pQi-1.ID;"<<endl;K.wi=wQi-1.ID;for(i=1;i<=n;i+)cin>>wi;K.cp=0;cout<<"最优解为(bestx)：K.cw=0;"<<endl;K.c=c;cout<

26、;<"最优值为(bestp)：K.n=n;"<<endl;K.bestp=0;cout<<Knapsack(p,w,c,n)<<endl;/回溯搜索cout<<"s重新开始K.Backtrack(1);"<<endl;K.print();cout<<"q退出 "<<endl;delete Q;cin>>k;delete K.w;delete K.p;4、运行结果如下图所示：方案四：分枝 -限界法1、分枝 -限界法的基本原理与分析分枝限

27、界发是另一种系统地搜索解空间的方法， 它与回溯法的主要区别在于对 E-结点 (expansion node)的扩充方式。 每个活结点有且仅有一次会变成 E-结点。当一个结点变为 E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出 ( 最优 )可行解的结点，其余结点加人活结点表，然后从表中选择一个结点作为下一个 E 结点。从活结点表中取出所选择的结点并进行扩充， 直到找到解或活动表为空， 扩充才结束。2、0-1 背包问题的实现0-1 背包问题的最大收益分枝定界算法可以使用定界函数来计算活结点的收益上限 upprofit ，使得以活结点为根的子树中的任一结点

28、的收益值都不可能超过 upprofit ，活结点的最大堆使用 upprofit 作为关键值域。在子集树中执行最大收益分枝定界搜索的函数首先初始化活结点的最大堆，并使用一个数组 bestx 来记录最优解。 由于需要不断地利用收益密度来排序，物品的索引值会随之变化，因此必须将函数所生成的结果映射回初始时的物品索引。函数中的循环首先检验 E-结点左孩子的可行性，如它是可行的，则将它加入子集树及活结点队列 (即最大堆 )，仅当结点右子树的定界值指明可能找到一个最优解时才将右孩子加入子集树和队列中。3、算法设计：#include <iostream.h>class Knap;int ID;f

29、loat d;/ 单位重量价值class Object;class Object;class bbnodefriendintKnapsack(int*,int*,int ,int ,int *);public:int operator <=(Object a)constfriend Knap;friendintKanpsack(int*,int*,int ,int ,int *);private:bbnode *parent;/指向父节点return (d >= a.d);的指针bool LChild;/ 左儿子结点private:标志;int*w;/物品重量class HeapN

30、ode数组int*p;/ 物品价值friend Knap;数组public:intcw;/ 当前背包operator int () const重量 return uprofit;intcp;/ 当前背包void Insert(HeapNode N);价值void DeleteMax(HeapNode N);int* bestx;/最优解的记private:录数组int uprofit,/结点的价值上界;profit;/ 结点所对应的/计算所相应的价值的上界价值int Knap:MaxBoundary(int i)int weight;/ 结点所对应的重量int cleft=c-cw;/ 剩余容

31、量int level;/ 活结点在子集int b=cp;/ 价值上限树中所处的层序号/ 以物品单位重量价值递减序bbnode *ptr;/指向活结点在装填剩余容量子集树中相应结点的指针while(i<=n&&wi<=cleft);void HeapNode:Insert(HeapNodecleft-=wi;N)b+=pi;i+;void/将背包的剩余容量装满HeapNode:DeleteMax(HeapNodif(i<=n)e N)b+=pi/wi*cleft;return b;class Knap/将一个新的活结点插入到子集树和优先队列中friend int

32、Knapsack(int*,intvoidKnap:AddLiveNode(int*,int ,int ,int *);up,int cp,int cw,bool ch,int lev)public:int MaxKnapsack();/ 将一个新的活结点插入到子private:集树和最大堆 H 中HeapNode *H;bbnode * b=new bbnode;int MaxBoundary(int i);b->parent=E;void AddLiveNode(intup,intb->LChild=ch;cp,int cw,bool ch,int level);HeapNod

33、e N;bbnode *E;/指向扩展N.uprofit=up;结点的指针N.profit=cp;int c;/背包容量N.weight=cw;int n;/物品总数N.level=lev;N.ptr=b;cw=N.weight;H->Insert(N);cp=N.profit;up=N.uprofit;/实施对子集树的优先队列式分i=N.level;支界限搜索int Knap:MaxKnapsack()/ 优先队列式分支界限法， 返回最大值， bestx 返回最优解/定义最大堆的容量为1000H=new HeapNode 1000;/构造当前最优解for(int j=n;j>0;

34、j-)bestxj=E->LChild;E=E->parent;/为 bestx 分配存储空间bestx=new int n+1;return cp;/初始化int i=1;/对数据进行预处理并完成调用E=0;MaxKnapsackcw=cp=0;intKnapsack(int p,intw,intint bestp=0;/当前最优解c,int n,int bestx)int up=MaxBoundary(1);/价值/ 返回最大值，bestx返回最优上界解/搜索子集空间树/初始化while(i!=n+1)/ 非叶结点int W=0;/ 装包物品重量int P=0;/装包物品价值/

35、 检查当前扩展结点的左/ 定义依单位重量价值排序的儿子结点物品数组int wt=cw+wi;if(wt<=c)Object * Q=new Objectn;for(int i=1;i<=n;i+)if(cp+pi>bestp)bestp=cp+pi;/单位重量价值数组Qi-1.ID=i;AddLiveNode(up,cp+pi,cw+wi,true,i+1);Qi-1.d=(float)1.0*pi/wi;P+=pi;W+=wi;up=MaxBoundary(i+1);/ 检查当前扩展结点的右if(W<=c)return P;/ 所有物品儿子结点if(up>=be

36、stp)装包/依单位重量价值排序float f;AddLiveNode(up,cp,cw,false,i+for( i=0;i<n;i+)1);for(int j=i;j<n;j+)/去下一个扩展结点HeapNode N;if(Qi.d<Qj.d)H->DeleteMax(N);E=N.ptr;f=Qi.d;Qi.d=Qj.d;Qj.d=f;void main()int m,n;/创建类 Knap 的数据成员Knap K;K.p=new int n+1;K.w=new int n+1;for(i=1;i<=n;i+)int i=0,j=0;int p100,w20

37、,x20;while(1)cout<<"0-1 背包问题递归法 "<<endl;K.pi=pQi-1.ID;cout<<" 请输入背包的容K.wi=wQi-1.ID;量： "<<endl;cout<<"请输入物品个数：K.cp=0;"<<endl;K.cw=0;cout<<" 请 输入物品的重K.c=c;量： "<<endl;K.n=n;cout<<" 请输入物品的价/调用MaxKnapsack 求

38、问题的值： "<<endl;最优解cout<<" 背包的最优解int bestp=K.MaxKnapsack();为:"<<endl<<Knapsack(p,w,m,n,for(int j=1;j<=n;j+)x)<<endl;cout<<" 最优解条件下选bestxQj-1.ID=K.bestxj;择的背包为:"<<endl;delete Q;for(i=1;i<=n;i+)delete K.w;cout<<xi<<&quo

39、t;t"delete K.p;cout<<endl;delete K.bestx;return bestp;4、运行结果如下图所示：三、四种算法的比较与分析这四种算法都得到了验证， 运行结果证明了算法设计是可行的， 正确的。通过对 O-1 背包问题的算法设计及时间复杂度分析可以看出。 无论采用贪婪法还是动态规划法，都是在已知约束条件下求解最大值建立数学模型算法实现的过程；但算法具体实现和数据结构的建立要用到递归和栈操作。 比较贪婪法和动态规划法。前者的时间复杂度低于后者， 从耗费上而言优于后者。 但后者的实现算法可读性要优于前者。动态规划算法的基本思想是把原问题分解为一系

40、列子问题， 然后从这些子问题中求出原问题的解。回溯其实就是穷举，穷举所有的解，找出解中最优的值。回溯法在包含问题的所有解的解空间树中， 按照深度优先的策略， 从根结点出发搜索解空间树。回溯法的基本思路是：确定解空间，建立解空间树，用深度优先搜索算法递归搜索解空间树，并同时注意剪枝 ,常用的分枝一限界法有最小耗费法，最大收益法。 FIFO(先进先出 )法等。 0-1 背包问题的分枝一限界算法可以使用最大收益算法。该算法跟回溯法类似。但分枝限界法需要O( 2n )的解空间。故该算法不常用在背包问题求解。 回溯法比分枝限界在占用内存方面具有优势。 回溯法占用的内存是 0(解空间的最大路径长度 )，而

41、分枝限界所占用的内存为 0(解空间大小 )。对于一个子集空间，回溯法需要 0(n)的内存空间，而分枝限界则需要 0(2n)的空间。虽然最大收益或最小耗费分枝限界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的结点， 但在实际应用中， 它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。通过以上对 0-1 背包问题的求解分析， 我们可以看到各种算法设计方法有各内不同的特点，针对不同的问题领域，它们有不同的效率，对于求解0-1 背包问题，各算法的时间复杂度、优缺点以及改进方法的比较如下表所示：算法时间复杂度动态规划O(minnc, 2 n ）回溯法O(n 2n ）分枝 - 限界

42、O( 2n ）法贪心算法O(nlogn）#include<iostream.h>#include<iostream>#include<stdio.h>#include<conio.h>#include<stdlib.h>#define max 100void sort (int n,float amax,float bmax)int j,h,k;float t1,t2,t3,cmax;优点缺点改进方法可求得最优决速度较慢建立动态规划策序列递归方程判断右子树能够获得最优时间复杂度较时，按效率密解高度 vi/wi 对剩余对象排序最大收益或

43、最速度较快，易占用的内存较小消耗分枝-求解大，效率不高限界法， FIFO法可以达到局部不能考虑到整对范围广的问体最优解，程最优解，用时题可以产生接序可读性低于少近的最优解动态规划/ 最多物品数/ 按价值密度排序for(k=0;k<n;k+)ck=ak/bk;for(j=0;j<n;j+)if(cj<cj+1)t1=aj;aj=aj+1;aj+1=t1;t2=bj;bj=bj+1;bj+1=t2;t3=cj;cj=cj+1;cj+1=t3;void knapsack(int n,float limitw,float vmax,float wmax,int xmax)float

44、c1; int i;/c1为背包剩余可装载重量sort(n,v,w);/物品按价值密度排序c1=limitw;for(i=0;i<n;i+)if(wi>c1)break;xi=1;/xi为 1 时，物品i 在解中c1=c1-wi;void main1()int n,i,xmax;float vmax,wmax,totalv=0,totalw=0,limitw;cout<<" 请输入 n 和总重量 :"cin>>n >>limitw;for(i=1;i<=n;i+)xi=0;/ 物品选择情况表初始化为0cout<&l

45、t;" 请依次输入物品的价值："<<endl;for(i=1;i<=n;i+)cin>>vi;cout<<endl;cout<<" 请依次输入物品的重量：for(i=1;i<=n;i+)cin>>wi;cout<<endl;knapsack (n,limitw,v,w,x);cout<<"the selection is:"for(i=1;i<=n;i+)cout<<xi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;"<<endl;cout<<endl;cout<<" 背包的总重量为：cout<<" 背包的总价值为："<<totalw<<endl; / "<<totalv<