0-1背包问的题目四种不同算法地实现

1、兰州交通大学数理与软件工程学院题 目0-1背包问题算法实现院系数理院专业班级信计09学生姓名雷雪艳学号200905130指导教师二0二年六月五日、问题描述：1、 0 1背包问题：给定n种物品和一个背包，背包最大容量为M，物 品i的重量是Wi,其价值是平Pi，问应当如何选择装入背包的物品，似的装 入背包的物品的总价值最大？背包问题的数学描述如下：2、要求找到一个n元向量(x1，x2-xn)，在满足约束条件：XiWiM0 x 1maxXi Pi0 Xi 1情况下，使得目标函数，其中，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 , 1 in， 要求找到一个n元0-1向量向量(x1，x2 -Xn)，X i =0 或1 , 1 i n,使 得xw M，而且X Pi达到最大2】、解决方案:方案一：贪心算法1、贪

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

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 ;然后，将物品进行排序，依贪心选择策略，将尽可能多的单位 重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去，直到

5、背包装满为止。3、算法设计如下：#in clude<iostream.h>#defi nemax100/最多物品数void sort (intn floatamax,float bmax)/按价值密度排序int j,h,k;float t1,t2,t3,cmax;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 kn apsack(i ntn floatlimitw,fl

6、oatvmax,floatwmax,i nt xmax)floatc1;c1为背包剩余可装载重量int i;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 mai n()int n ,i,xmax;floatvmax,wmax,totalv=0,totalw=0,limitw;cout«"请输入 n 和 limitw:"cin>>n >>limitw;for(i=1;i<=n

7、;i+)xi=0;/物品选择情况表初始化为0 coutvv"请依次输入物品的价 值："<<endl;for(i=1;i<=n ;i+)cin> >vi;cout«e ndl;coutvv"请依次输入物品的重量："<<endl;for(i=1;i<=n ;i+)cin> >wi;coutvve ndl;kn apsack (n ,limitw,v,w,x);4、贪心算法运行结果如下图所示: cout<<"the selectio n is:"for(i=1

8、;i<=n ;i+)cout<<xi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;coutvve ndl;coutvv"背包的总重量为："vvtotalwvvendl; / 背包所装载总重量coutvv"背包的总价值为： "vvtotalvvvendl; / 背包的总 价值请低抄:愉入物品的車量149the 总左丄ection Is：11U 背就的总車凰为，76 背包的总价值为 65 PreHM dii V le y Lu cun t 丄方案二：动态规划算法1、动态规划的基本原理与分析动态规划算法

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

10、值； 构造最优解。2、0-1背包问题的实现最优子结构性质0-1背包问题具有最优子结构性质。设(y1 , y2-yn)是所给0-1背包问 题的一个最优解，则(y2 , y3yn)是下面相应子问题的一个最优解：nmax VkXkk inWkXkjk iXk 0,1, i k n因若不然，设(z2 , z3zn)是上述问题的一个最优解，而(y2 , y3n)不是nnvi yiw1y1wi z它的最优解，由此可见i 2，且2C。因此nnvlylVi ZiViyii 2i 1nwlylwi zi 2 c这说明(y1 , z2-zn)是所给0-1背包问题的一个更优解，从而(y1 , y2yn)不是所给0-

11、1背包问题的最优解。此为矛盾1递归关系设所给0-1背包问题的子问题nmaxVkXkk inWkXkjk iXk0,1, i k n的最优值为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, j wi)m(i,j)vnj wn m(n,j).0 j wn3、算法设计如下：#in clude<iostream>#i ncludevioma nip>using n amespace std;const int MAX=

12、1000;intwMAX,vMAX,bestMAX;int VMAXMAX; / 最大价值矩阵int W,n;/W为背包的最大载重量，n为物品的数量/求最大值函数int max(i nt x,i nt y)retur n x >= y?x:y;/求最小值函数vi, j wim(i 1 j),0 j wjretur n x>= y ? y:x;void Kn aspack()int Max=mi n(w n-1,W);for(i nt j=1; j <= Max ; j+)V nj=0;for(j=wn; j <= W ; j+)V nj=v n;for(i nt i=n

13、-1;i > 1 ; i-)Max=mi n(wi-1,W);for( j=1; j <= Max ; j+)Vij=Vi+1j;for( j=wi; j <= W; j+)Vij=max(Vi+1j,Vi+1int min (i nt x,i nt y)j-wi+vi);V1W=V2W;/ 先假设第一个物品不放入if(W > w1)V1W=max(V1W,V2W-w1+v1);/生成向量数组，决定某一个物 品是否应该放入背包void Traceback()for(i nt i=1; i < n ; i+)/比较矩阵两邻两行(除最后一 行)，背包容量为W的最优值.

14、if(ViW = Vi+1W)/如果当前行的最优值与下一 行的最优值相等，则表明该物品 不能放入。else/否则可以放入besti=1;W-=wi;bestn=(VnW )?1:0;void mai n()cout«"输入商品数量 n和背包容量W:"cin»n>>W;coutvv"输入每件商品的重量 w:"<<endl;for(int i=1;i<=n;i+)ci n> >wi;memset(V,0,sizeof(V);coutvv"输入每件商品的价值 v:"<<

15、;endl;besti=0;for( i=1;i<=n ;i+)cin> >vi;Knaspack();构造矩阵Traceback(); /求出解的向量数组int totalW=0;int totalV=0;/显示可以放入的物品cout«"所选择的商品如下:"<<e ndl;coutvv"序号i:重量w:价格 v:"<<e ndl;for(i=1; i <= n ; i+)if(besti = 1)totalW+=wi;4、计算复杂性分析totalV+=vi;cout<<setiosf

16、lags(ios:left) <<setw(5)<<i<<""<<wi<<""<<vi<<e ndl;cout«"放入的物品重量总和是:"vvtotalWvv" 价值最 优解是:"<<V1W<<" "vvtotaIVvve ndl;利用动态规划求解0-1背包问题的复杂度为0(minnc,2n。动态规划主 要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立 动态规划

17、递归方程，它可以帮助高效地解决问题8。5、动态规划运行结果如下图所示：81 C;Progranri F lesMiVisual Studi-oMyProjectscvDcbugexew车俞入 商品审n和背包容号VJ： 3N7 嗇人営祥商翥的重量32J 6U 56输人每件商品的价值*序号1 5 B W :彳介榕U :1 23342 6Q65放入的槻启重量总和是，叮价值最优解是詛站Press -am key to cont ±nu.eH方案三：回溯法1、回溯法的基本原理与分析回溯是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题 定义一个解空间，这个解空间必须至少包含问题的一个

18、解（可能是最优的）。回溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解 （可能是最优的）。使用递归回溯法解决背包问题的优点在于它算法思想简单， 而且它能完全遍历搜索空间，肯定能找到问题的最优解奉但是由于此问题解 的总组合数有2n个,因此随着物件数n的增大，其解的空间将以门2"级增长, 当n大到一定程度上，用此算法解决背包问题将是不现实的。下一步是组织解空间以便它能被容易地搜索。 典型的组织方法是图或树。 一旦定义了解空间的组织方法，这个空间即可按照深度优先的方法从开始结 点进行搜索，利用限界函数避免移动到不可能产生解的子空间。2、0-1背包问题的实现回溯法是一种系统地

19、搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解（可能是最优的）。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包， 以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含 有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简 单方法是r为还未遍历的对象的收益之和，将 r加到cp （当前节点所获收益） 之上，若（叶cp） be

20、stp（目前最优解的收益），则不需搜索右子树。一种更 有效的方法是按收益密度vi/wi对剩余对象排序，将对象按密度递减的顺序 去填充背包的剩余容量，当遇到第一个不能全部放人背包的对象时，就使用它的一部分。3、算法设计如下：#in clude<iostream>using n amespace std;class Knapfriend int Kn apsack(i nt p,i ntw,i nt c,i nt n );public:void prin t()cout«e ndl;private:int Boun d(i nt i);void Backtrack©

21、 nt i);int c;/背包容量int n; /物品数int *w;/物品重量数组int *p;/物品价值数组int cw;/当前重量cout<<bestxmvv""int cp;/当前价值int bestp;/当前最优值int *bestx;/当前最优解int *x;/当前解；int Kn ap:Bo un d(i nt i)/计算上界in t cleft=c-cw;剩余容量int b=cp;/以物品单位重量价值递减序 装入物品while(i<=n&&wiv=cleft)cleft-=wi;b+=pi;i+;/装满背包if(i<

22、=n)b+=pi/wi*cleft;return b;void Kn ap:Backtrack(i nt i)if(i> n)if(bestp<cp)for(i nt j=1;j<=n ;j+)bestxj=xj;bestp=cp;return;if(cw+wi<=c) /搜索左子树xi=1;cw+=wi;cp+=pi;Backtrack(i+1);cw_=wi;cp-=pi;if(Bou nd(i+1)>bestp)搜索右子树xi=O;Backtrack(i+1);class Objectfrie nd int Kn apsack(i nt p,i ntw,i

23、nt c,i nt n);public:intoperator<=(Objecta)c onstreturn (d>=a.d);private:int ID;float d;intKn apsack(i ntp,i nt/ 为 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

24、<n ;i+)for(i nt j=i;j< n;j+)if(Qi.d<Qj.d)w,i nt c,i nt n)f=Qi.d;/回溯搜索Qi.d=Qj.d;K.Backtrack(1);Qj.d=f;K.pri nt();delete Q;delete K.w;Knap K;delete K.p;K.p = new intn+1;return K.bestp;K.w = new in t n+1;K.x = new intn+1;void mai n()K.bestx = new in t n+1;K.xO=O;int *p;K.bestxO=O;int *w;for( i

25、=1;i<=n ;i+)int c=0;int n=0;K.pi=pQi-1.ID;int i=0;K.wi=wQi-1.ID;char k;while(k)K.cp=0;K.cw=0;cout«"请输入背包容量（c）:K.c=c;"<<e ndl;K. n=n;cin> >c;K.bestp=0;coutvv"请输入物品的个数(n): "<<endl;cin»n;p=new in t n+1;w=new in t n+1;p0=0；w0=0;coutvv"请输入物品的价值(p):

26、"<<endl;for(i=1;i<=n ;i+)cin> >pi;cout«"请输入物品的重量(w): "<<endl;for(i=1;i<=n ;i+)4、运行结果如下图所示：cin> >wi;cout«" 最优解为(bestx):"<<e ndl;cout«" 最优值为(bestp):"<<e ndl;cout«K napsack(p,w,c ,n)<<en dl;cout<&l

27、t;"s 重新开始"<<e ndl;cout«"q退出"<<endl;cin> >k;请输入背包容量J儿90苹输入物en的个数<">< 量蹩物品的价值 3, 请输入物品的重量78 5曇如舞再5*七9 I 駆/忧值 Ki 5*七卩& 1二】重拈幵贻方案四：分枝-限界法1、分枝-限界法的基本原理与分析分枝限界发是另一种系统地搜索解空间的方法，它与回溯法的主要区别在 于对E-结点（expansion node）的扩充方式。每个活结点有且仅有一次会变成 E-结点。当一个结点变为E-

28、结点时，则生成从该结点移动一步即可到达的所 有新结点。在生成的结点中，抛弃那些不可能导出（最优河行解的结点，其余结点加人活结点表，然后从表中选择一个结点作为下一个E结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结 束。2、0-1背包问题的实现0-1背包问题的最大收益分枝定界算法可以使用定界函数来计算活结点 的收益上限upprofit，使得以活结点为根的子树中的任一结点的收益值都不 可能超过upprofit ，活结点的最大堆使用upprofit作为关键值域。在子集树 中执行最大收益分枝定界搜索的函数首先初始化活结点的最大堆，并使用一 个数组bestx来记录最优解。由

29、于需要不断地利用收益密度来排序，物品的 索引值会随之变化，因此必须将函数所生成的结果映射回初始时的物品索引。 函数中的循环首先检验E-结点左孩子的可行性，如它是可行的，则将它加入 子集树及活结点队列（即最大堆），仅当结点右子树的定界值指明可能找到一 个最优解时才将右孩子加入子集树和队列中。3、算法设计：#i nclude <iostream.h>class Kn ap;class Object;class Objectfrie nd int Kn apsack(i nt *,i nt*,i nt ,i nt ,int *);public:int operator v=(Object

30、a)c onstreturn (d >= a.d);private:int ID;float d;单位重量价值;class bbnodefrie nd Kn ap;frie nd int Kan psack(i nt *,i nt*,i nt ,i nt ,int *);private:bbnode * pare nt;指向父节点的指针bool LChild; / 左儿子结 点标志;class HeapNodefrie nd Kn ap;public:operator int () const retur n uprofit;void In sert(HeapNode N);voidDe

31、leteMax(He apNode N);private:int uprofit,/结点的价值上界profit; /结点所对应的价值int weight; /结点所对应的重量int level; /活结点在子集树中所处的层序号bbnode * ptr; / 指向活结点在子集树中相应结点的指针;voidHeapNode:l nsert(HeapNode N)voidHe apNode:DeleteMax(HeapNode N)class Knapfrie nd int Kn apsack(i nt *,i nt*,i nt ,i nt ,int *);public:int MaxK napsac

32、k();private:Heap Node *H;int MaxBo un dary(i nt i);voidAddLiveNode(i ntup,i nt cp,i nt cw,bool ch,i nt level);bbnode * E; / 指向扩 展结点的指针int c;/背包容量int n;/物品总数int *w;/物品重量数组int *p;/物品价值数组int cw;/当前背包重量int cp;/当前背包价值int * bestx;/最优解的记录数组;/计算所相应的价值的上界int Kn ap:MaxBo un dary(i nt i)int cleft=c-cw; / 剩余容量i

33、nt b=cp;/ 价值上限/以物品单位重量价值递减序装填剩余容量while(i<=n&&wi<=cleft)cleft-=wi;b+=pi;i+；/将背包的剩余容量装满if(i<=n)b+=pi/wi*cleft;return b;/将一个新的活结点插入到子集树和优先队列中void Kn ap:AddLiveNode(i ntup,i nt cp,i nt cw,bool ch,i ntlev)/将一个新的活结点插入到子集树和最大堆H中bbnode * b=new bbno de;b->pare nt=E;b->LChild=ch;HeapNod

34、e N;N.uprofit=up;N.profit=cp;N.weight=cw;N.level=lev;N.ptr=b;H->I nsert(N);/实施对子集树的优先队列式分支界限搜索int Kn ap:MaxK napsack()/优先队列式分支界限法，返回最大值，bestx返回最优解/定义最大堆的容量为1000H=new HeapNode 1000;/为bestx分配存储空间bestx=new int n+1;/初始化int i=1;E=0;cw=cp=0;int bestp=0; / 当前最优解int up=MaxBoundary(1);价值上界/搜索子集空间树while(i!

35、=n+1)非叶结点/检查当前扩展结点的左 儿子结点int wt=cw+wi;if(wt<=c)if(cp+pi>bestp)bestp=cp+pi;AddLiveNode(up,cp+pi,cw+wi,true,i+1);up=MaxBo un dary(i+1);/检查当前扩展结点的右儿子结点if(up>=bestp)AddLiveNode(up,cp,cw,false,i+1);/去下一个扩展结点HeapNode N;H->DeleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofit; i=N.level;/构造

36、当前最优解for(i nt j=n ;j>O;j-)bestxj=E->LChild;E=E->pare nt;return cp;/对数据进行预处理并完成调用 MaxK nap sackintKn apsack(i ntp,i ntfloat f;for( i=0;i< n;i+)for(i nt j=i;j< n;j+)if(Qi.d<Qj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;/创建类Knap的数据成员Knap K;K.p=new int n+1;K.w=new int n+1; for(i=1;i<=n ;i+)K.pi=pQi-

37、1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;w,i nt c,i nt n ,i nt bestx)/返回最大值，bestx返回最优解/初始化int W=0;/装包物品重量int P=0;/装包物品价值/定义依单位重量价值排序的物品数组Object * Q=new Object n;for(int i=1;i<=n;i+)/单位重量价值数组Qi-1.ID=i;Qi-1.d=(float)1.0*pi/wiJP+=pi；W+=wi;if(W<=c) return P;/ 所有物品装包/依单位重量价值排序K.c=c;K. n=n;/调用MaxKnapsack求问题

38、的最优解intbestp=K.MaxK napsack();for(i nt j=1;j<=n ;j+)bestxQj-1.ID=K.bestxj;delete Q;delete K.w;delete K.p;delete K.bestx;return bestp;void mai n()int m,n;int i=0,j=0;in t p100,w20,x20;while(1)cout<<"0-1 背包问题一递归法"<<endl;cout«"请输入背包的容量："<<endl;coutvv"请

39、输入物品个数： "<<e ndl;coutvv"请输入物品的重 量："<<endl;coutvv"请输入物品的 价值："<<endl;coutvv"背包的最优 解为："vvendlvvKnapsack(p,w, m,n, x)vve ndl;coutvv"最优解条件下选择的背包为:"vvendl;for(i=1;iv=n ;i+)coutvvxivv"t" coutvve ndl;4、运行结果如下图所示:intip31 23们呻3船$5 n 31 4

40、35占殆to14帰 邑品.JLrnn半 f X 背翱夠直孑措爲 A'入入入背上价S 釉锚歸枣.，优CS三、四种算法的比较与分析这四种算法都得到了验证，运行结果证明了算法设计是可行的，正确的。通过对0-1背包问题的算法设计及时间复杂度分析可以看出。无论采用贪婪法还 是动态规划法，都是在已知约束条件下求解最大值建立数学模型算法实现的过 程；但算法具体实现和数据结构的建立要用到递归和栈操作。比较贪婪法和动态规划法。前者的时间复杂度低于后者，从耗费上而言优于后者。但后者的实现算 法可读性要优于前者。动态规划算法的基本思想是把原问题分解为一系列子问题，然后从这些子问题中求出原问题的解。回溯其实就

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

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

43、按效率密度vi/wi对剩余对象排序分枝-限界法O(2)速度较快，易求解占用的内存较大，效率不咼最大收益或最 小消耗分枝-限界法，FIFO法贪心算法O(nlogn )可以达到局部最优解，用时少不能考虑到整 体最优解，程 序可读性低于 动态规划对范围广的问题可以产生接近的最优解#in clude<iostream.h>#in clude<iostream>#in clude<stdio.h>#in clude<c oni o.h>#in clude<stdlib.h>#define max 100/最多物品数void sort (int

44、n,float amax,float bmax)/ 按价值密度排序int j,h,k;float t1,t2,t3,cmax;for(k=0;k< n; k+)ck=ak/bk;for( j=0;j<n;j+)if(cj<cj+1)t1=a j;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 c1; int i;c1为背包剩余可装载重量sort( n,v,w);/物品

45、按价值密度排序c1=limitw;for(i=0;i< n;i+)if(wi>c1)break;xi=1;xi为1时，物品i在解中c1=c1-wi;void ma in 1()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;/cout<<" 请依次输入物品的价值："<<e ndl;for(i=1;i<=

46、n ;i+)cin> >vi;cout<<e ndl;cout<<" 请依次输入物品的重量："<<e ndl;for(i=1;i<=n ;i+)cin> >wi;cout<<e ndl;kn apsack (n ,limitw,v,w,x);cout<<"the select ion is:"for(i=1;i<=n ;i+)cout<<xi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;cout<<

47、;e ndl;背包所装载总重量背包的总价值cout<<"背包的总重量为："<<totalw<<e ndl; /cout<<"背包的总价值为："<<totalv<<e ndl; / using n amespace std;class Knapfriend int Kn apsack(i nt p,i nt w,i nt c,i nt n );public:void prin t()for(i nt m=1;m <=n; m+)cout<<bestxm<<

48、""cout<<e ndl;private:int Boun d(i nt i);void Backtrack(i nt i);int c;/背包容量int n; /物品数int *w;物品重量数组int *p;物品价值数组int cw; 当前重量in t cp;/当前价值int bestp;/当前最优值int *bestx;当前最优解int *x;当前解；int Kn ap:Bo un d(i nt i)/计算上界in t cleft=c-cw; 剩余容量int b=cp;/以物品单位重量价值递减序装入物品 while(i<=n&&wi&

49、lt;=cleft) cleft-=wi;b+=pi;i+;/装满背包 if(i<=n)b+=pi/wi*cleft;return b;void Kn ap:Backtrack(i nt i)if(i> n)if(bestp<cp)for(i nt j=1;j<=n ;j+)bestxj=xj;bestp=cp;return;if(cw+wi<=c) /搜索左子树xi=1;cw+=wi;cp+=pi;Backtrack(i+1);cw-=wi;cp-=pi;if(Bou nd(i+1)>bestp)搜索右子树xi=O;Backtrack(i+1);class

50、 Objectfriend int Kn apsack(i nt p,i nt w,i nt c,i nt n);public:int operator<=(Object a)c onstreturn (d>=a.d);private:int ID;float d;int Kn apsack(i nt p,i nt w,i nt c,i nt n)/ 为 Knap:Backtrack 初始化int W=0;int P=0;in t i=1;Object *Q=new Objectn;for(i nt i=1;i<=n ;i+)Qi-1D=i;Qi-1.d=1.0*pi/wi;

51、P+=pi；W+=wi;if(W<=c)return P;/ 装入所有物品/依物品单位重量排序float f;for( i=0;i< n; i+)for(i nt j=i;j< n;j+)if(Qi.d<Q j.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;Knap K;K.p = new intn+1;K.w = new in t n+1;K.x = new intn+1;K.bestx = new in t n+1;K.xO=O;K.bestxO=O;for( i=1;i<=n ;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0

52、;K.cw=0;K.c=c;K.n=n;K.bestp=0;/回溯搜索K.Backtrack(1);K.pri nt();delete Q;delete K.w;delete K.p;return K.bestp;void mai n2()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;

53、p=new intn +1;w=new intn+1;p0=0;w0=0;cout<<" 请输入物品的价值(p) : "<<endl;for(i=1;i<=n ;i+)cin> >pi;cout<<" 请输入物品的重量(w) : "<<endl;for(i=1;i<=n ;i+)cin> >wi;cout<<"最优解为(bestx) : "<<endl;cout<<"最优值为(bestp) : "<<endl;cout<<K napsack(p,w,c, n)<<en dl;cout<<"s 重新开始"<<endl;cout<<"q退出"<<