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

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

2、，背包的 容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最 大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i装人背包多次，也不能只装入部分的物品i。该 问题称为0-1背包问题。0-1背包问题的符号化表示是，给定 M0， w i 0， pi 0，1勻兰n， 要求找到一个n元0-1向量向量（x1，x2xn）， X i =0或1 ,仁2 n,使得Z，而且X Pi达到最大2。、解决方案：方案一：贪心算法1、贪心算法的基本原理与分析贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最 优解上加以考虑，它所作出的选择只是在某种意义上的局部

3、最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产 生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部 最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素， 也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该 冋题可用动态规划算法或贪心算法求解的关键特征。2、0-1背包问题的实现对于0-1背包问题，

4、设A是能装入容量为c的背包的具有最大价值的物 品集合，则Aj=A-j是n-1个物品1,2，,j-1,j+1,n可装入容量为c-wj的背 包的具有最大价值的物品集合。用贪心算法求解0-1背包问题的步骤是，首先计算每种物品单位重量的 价值vi/wi ;然后，将物品进行排序，依贪心选择策略，将尽可能多的单位 重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直进行下去，直到背包装满为止。3、算法设计如下：#in clude#defi nemax100最多物品数void sort (i nt n, float

5、 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(cjcj+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;voidkn apsack(i ntn floatlimitw,floatvmax,floatwmax,i nt xmax)floatc1;c1为背包剩余可装载重量int i;sort( n, v,w);物品按价值密度排序c1=limitw;for(i=0

6、;ic1)break;xi=1;/xi为1时，物品i在解中c仁 c1-wi;void mai n()int n ,i,xmax;4、贪心算法运行结果如下图所示:floatvmax,wmax,totalv=O,totalw=O ,limitw;cout请输入 n 和 limitw:; cinn limitw;for(i=1;i=n ;i+) xi=0;物品选择情况表初始化为0 cout请依次输入物品的价值：e ndl;for(i=1;i vi;coute ndl;cout请依次输入物品的重量：e ndl; for(i=1;i wi; coute ndl;kn apsack (n ,limitw,

7、v,w,x); coutthe selectio n is:; for(i=1;i=n ;i+)coutxi;if(xi=1) totalw=totalw+wi; totalv=totalv+vi;coute ndl;cout背包的总重量为： vvtotalwvvendl; /背包所装载 总重量cout背包的总价值为： vvtotalvvve ndl; /背包的总价值 c：%请输入 nllriitw = 3 89 请裱次输入物品的价值23 42 2请依次输入物品的重星:4G 31 49t;he siE lee: 1b Id n is = 110背包的总重量为二VG背包的总价值为=GSP*ass

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

9、问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下： 分析最优解的结构：最有子结构性质； 建立递归方程； 计算最优值； 构造最优解O2、0-1背包问题的实现最优子结构性质0-1背包问题具有最优子结构性质。设（y1，y2yn）是所给0-1背包问 题的一个最优解，则（y2，y3yn）是下面相应子问题的一个最优解：nmaxVkXkk 土Xk 0,1, i v, y,w1y1 、 Wj z的最优解，由此可见 * v，且 乞Co因此nnv1y1 亠二 Vi 乙二 Vi yi2i dwlyl wzy wim(i,j)=km(i+1,j),0 jcwjvnj wnm( n,j).0 j w n3

10、、算法设计如下：#in clude#i ncludevioma nip using n amespace std;const int MAX=1000;int wMAX,vMAX,bestMAX;int VMAXMAX; /最大价 值矩阵int W,n;/W为背包的最大载重量，n为物品 的数量求最大值函数int max(i nt x,i nt y)retur n x = y?x:y;求最小值函数int min (i nt x,i nt y)retur n x= y ? y:x;void Kn aspack()int Max=mi n(w n-1,W);for(i nt j=1; j = Max

11、 ; j+)V nj=0;for( j=wn; j 1 ; i-)Max=mi n(wi-1,W);for( j=1; j = Max ; j+)Vij=Vi+1j;for( j=wi; j w1)V1W=max(V1W,V2 W-w1+v1);生成向量数组，决定某一个物 品是否应该放入背包void Traceback()for(i nt i=1; i nW;coutvv输入每件商品的重量for(int i=1;i wi;memset(V0,sizeof(V);coutvv输入每件商品的价值 v:e ndl;for( i=1;i vi;Kn aspack();构造矩阵 Traceback();

12、 /求出解的向 量数组int totalW=0;int totalV=0;显示可以放入的物品coutvv所选择的商品如 下:vve ndl;coutvv序号i:重量 w:价格 v:vve ndl;for(i=1; i v= n ; i+)if(besti = 1)totalW+=wi; totalV+=vi;coutvvsetiosflags(ios:left)vvse tw(5) vvivvvvwivvvvvivve ndl;coutvv放入的物品重量总和 是:vvtotalWvv 价值最优解 是:vvV1WvvvvtotalVvve ndl;方案三：回溯法1、回溯法的基本原理与分析回溯是一

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

14、索，利用限界函数避免移动到不可能产生解的子空间。2、0-1背包问题的实现回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为 问题定义一个解空间，这个解空间必须至少包含问题的一个解（可能是最优的）。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包， 以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归 算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改 进后的代码可找到获得最大收益时包含在背包中的对象的集合。左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含 有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简 单方

15、法是r为还未遍历的对象的收益之和，将 r加到cp （当前节点所获收益） 之上，若（叶cp）乞bestp（目前最优解的收益），则不需搜索右子树。一种更有 效的方法是按收益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填 充背包的剩余容量，当遇到第一个不能全部放人背包的对象时，就使用它的一部分。3、算法设计如下：w,i nt c,i nt n ); public:void prin t()for(i nt m=1;m v=n; m+)#in clude using n amespace std; class Knapfriend int Knapsack(int p,intcoutbest

16、xmvv; coute ndl;；private:int Boun d(i nt i);void Backtrack nt i);in t 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=cleft)cleft-=wi;b+=pi;i

17、+;装满背包if(i n)if(bestpcp)for(i nt j=1;j=n ;j+) bestxj=xj; return; if(cw+wibestp) 搜索右 子树xi=0;Backtrack(i+1);class Objectfriend int Knapsack(int p,int w,i nt c,i nt n);public:int operator=a.d);private:int ID;float d;int Knapsack(int p,int w,int c,i nt n)为 Knap:Backtrack 初始化 int W=0;int P=0;int i=1;Obje

18、ct *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(i nt j=i;j n;j+)if(Qi.dQj.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.x0=0;K.bestx0=0;for( i=1;i=

19、n ;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0;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;4、运行结果如下图所示：return K.bestp;void mai n()int *p;int *w;int c=0;int n=0;int i=0;char k;while(k)cout请输入背包容量(c): c;coutvv请输入物品的个数(n): n;p=new intn+1;w=new in t n+1;p0=0;w0=

20、0;coutvv请输入物品的价值(p): e ndl;for(i=1;i pi;coutvv请输入物品的重量(w): e ndl;for(i=1;i wi;coutvv最优解为(bestx): k;方案四：分枝-限界法1、分枝-限界法的基本原理与分析分枝限界发是另一种系统地搜索解空间的方法，它与回溯法的主要区别在 于对E-结点（expansion node的扩充方式。每个活结点有且仅有一次会变成 E- 结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有 新结点。在生成的结点中，抛弃那些不可能导出（最优河行解的结点，其余结点加人活结点表，然后从表中选择一个结点作为下一个E结点。

21、从活结点表中取出所选择的结点并进行扩充， 直到找到解或活动表为空，扩充才结束。2、0-1背包问题的实现0-1背包问题的最大收益分枝定界算法可以使用定界函数来计算活结点的 收益上限upprofit，使得以活结点为根的子树中的任一结点的收益值都不可能 超过upprofit，活结点的最大堆使用upprofit作为关键值域。在子集树中执行 最大收益分枝定界搜索的函数首先初始化活结点的最大堆，并使用一个数组bestx来记录最优解。由于需要不断地利用收益密度来排序，物品的索引值会 随之变化，因此必须将函数所生成的结果映射回初始时的物品索引。函数中 的循环首先检验E-结点左孩子的可行性，如它是可行的，则将它

22、加入子集树 及活结点队列（即最大堆），仅当结点右子树的定界值指明可能找到一个最优解时才将右孩子加入子集树和队列中3、算法设计：#i nclude class Kn ap;class Object;class Objectfriend int Knapsack(int *,int*,i nt ,i nt ,int *);public:int operator = a.d);private:int ID;float d;单位重量价值 ;class bbnodefrie nd Kn ap;friend int Kanpsack(int *,int *,i nt ,i nt ,int *); priv

23、ate:bbnode * pare nt;/指向父节点 的指针bool LChild;/左儿子结点标志;class HeapNodefrie nd Kn ap;public:operator int () const retur n uprofit;void In sert(HeapNode N);void DeleteMax(He apNode N); private:int uprofit,/结点的价值上界profit;/结点所对应的价值int weight;/结点所对应的重量int level;/活结点在子集树中所处的层序号bbnode * ptr; 指向活结点在 子集树中相应结点的指针

24、;void HeapNode:l nsert(HeapNodeN)voidHe apNode:DeleteMax(He apNod e N)class Knapfriend int Knapsack(int *,int*,i nt ,i nt ,int *);public:int MaxK napsack();private:Heap Node *H;int MaxBo un dary(i nt i);void AddLiveNode(int up,int cp,i nt cw,bool ch,i nt level);bbnode * E;指向扩展结点的指针int c;背包容量int n;/物

25、品总数int *w;/物品重量数组int *p;/物品价值数组int cw;/当前背包重量int cp;/当前背包价值int * bestx;/最优解的记录数组;计算所相应的价值的上界int Kn ap:MaxBo un dary(i nt i)in t cleft=c-cw;/ 剩余容量int b=cp;/价值上限/以物品单位重量价值递减序 装填剩余容量while(i=n&wi=cleft)cleft-=wi;b+=pi;i+;将背包的剩余容量装满if(ipare nt=E;b-LChild=ch;HeapNode N;N.uprofit=up;N.profit=cp;N.weight=cw

26、;N.level=lev;N.ptr=b;H-l 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!=n+1)/ 非叶结点/检查当前扩展结点的左 儿子结点int wt=cw+wi;if(wt

27、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;构造当前最优解for(i nt j=n ;j0;j-)bestxj=E-LChild;E=E-pare nt;return cp;/对数据

28、进行预处理并完成调用MaxK napsackint Knapsack(int p,int w,int c,i nt n ,i nt bestx)/返回最大值，bestx返回最优 解初始化int W=0;/装包物品重量int P=0; /装包物品价值/定义依单位重量价值排序的 物品数组Object * Q=new Objectn; for(int i=1;i=n;i+)单位重量价值数组Qi-1.ID=i;Qi-1.d=(float)1.0*pi/wi;P+=pi;W+=wi;if(W=c) return P;/所有物品 装包/依单位重量价值排序float f;for( i=0;i n;i+)fo

29、r(i nt j=i;j n;j+)if(Qi.dQj.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-1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K. n=n;/调用MaxK nap sack求问题的 最优解int bestp=K.MaxK napsack(); for(i nt j=1;j=n ;j+)bestxQj-1.ID=K.bestxj; delete Q;delete K.w;delete

30、K.p;delete K.bestx;return bestp;4、运行结果如下图所示：void mai n()int m,n;int i=0,j=0;in t p100,w20,x20;while(1)cout0-1背包问题 递归法e ndl;cout请输入背包的容量：endl;cout请输入物品个数： e ndl;coutvv请输入物品的重 量：endl;cout请输入物品的价值：endl;coutvv背包的最优解 为：endlvvKnapsack(p,w,m,n, x)e ndl;coutvv最优解条件下选 择的背包为:endl;for(i=1;i=n ;i+) coutxivvt;co

31、utvve ndl;irm裁21 23 33 43 45 5531 33 43 53 55 65cont包品品品的包 3 入入入入背2 黑荊枣.1三、四种算法的比较与分析这四种算法都得到了验证，运行结果证明了算法设计是可行的， 正确的。通 过对0-1背包问题的算法设计及时间复杂度分析可以看出。无论采用贪婪法还是 动态规划法，都是在已知约束条件下求解最大值建立数学模型算法实现的过程； 但算法具体实现和数据结构的建立要用到递归和栈操作。比较贪婪法和动态规划 法。前者的时间复杂度低于后者，从耗费上而言优于后者。但后者的实现算法可 读性要优于前者。动态规划算法的基本思想是把原问题分解为一系列子问题，然

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

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

34、 2n)能够获得最优 解时间复杂度较 高判断右子树 时，按效率密 度vi/wi对剩 余对象排序分枝-限界 法O(2n)速度较快，易 求解占用的内存较 大，效率不咼最大收益或最 小消耗分枝-限界法，FIFO法贪心算法O( nlogn)可以达到局部 最优解，用时 少不能考虑到整 体最优解，程 序可读性低于 动态规划对范围广的问 题可以产生接 近的最优解#in clude#in clude#in clude#in clude#in clude#defi ne max 100/最多物品数void sort (int n,float amax,float bmax)/ 按价值密度排序int j,h,k;

35、float t1,t2,t3,cmax;for(k=0;kn;k+)ck=ak/bk;for(j=0;jn;j+)if(cjcj+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 c1; int i;/c1 为背包剩余可装载重量sort(n,v,w);/物品按价值密度排序c1=limitw;for(i=0;ic1)break;xi=1; /xi 为1时，物品 i 在解中

36、c1=c1-wi;void main1()int n,i,xmax;float vmax,wmax,totalv=0,totalw=0,limitw;coutn limitw;for(i=1;i=n;i+)xi=0;/ 物品选择情况表初始化为 0cout 请依次输入物品的价值： endl;for(i=1;ivi;coutendl;cout 请依次输入物品的重量： endl;for(i=1;iwi;coutendl;knapsack (n,limitw,v,w,x);coutthe selection is:;for(i=1;i=n;i+)coutxi;if(xi=1)totalw=totalw

37、+wi;totalv=totalv+vi;coutendl;cout 背包的总重量为： totalwendl; / 背包所装载总重量 cout 背包的总价值为： totalvendl; / 背包的总价值 using namespace std;class Knapfriend int Knapsack(int p,int w,int c,int n ); public:void print()for(int m=1;m=n;m+)coutbestxm ;coutendl; private: int Bound(int i);void Backtrack(int i);int c;/ 背包容量i

38、nt n; / 物品数int *w;/ 物品重量数组int *p;/ 物品价值数组int cw;/ 当前重量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(in)if(bestpcp)for(int j=1;j=n;j+) bestxj=xj; bestp=cp;return;i

39、f(cw+wibestp)/ 搜索右子树xi=0;Backtrack(i+1);class Objectfriend int Knapsack(int p,int w,int c,int n); public:int operator=a.d); private: int ID; float d;int Knapsack(int p,int w,int c,int n) /为 Knap:Backtrack 初始化 int W=0;int P=0; int i=1;Object *Q=new Objectn; for(int i=1;i=n;i+) Qi-1.ID=i;Qi-1.d=1.0*pi

40、/wi;P+=pi; W+=wi; if(W=c) return P;/ 装入所有物品 /依物品单位重量排序 float f;for( i=0;in;i+) for(int j=i;jn;j+)if(Qi.dQj.d) f=Qi.d;Qi.d=Qj.d;Qj.d=f; Knap K;K.p = new intn+1;K.w = 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+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.

41、c=c; K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1);K.print(); delete Q; delete K.w; delete K.p; return K.bestp; void main2() int *p; int *w;int c=0; int n=0; int i=0; char k; while(k) cout 请输入背包容量 (c)： c;cout 请输入物品的个数 (n)： n;p=new intn+1; w=new intn+1;p0=0; w0=0;cout 请输入物品的价值 (p)： endl; for(i=1;ipi;cout 请输

42、入物品的重量 (w) ： endl; for(i=1;iwi; cout 最优解为 (bestx)： endl; cout 最优值为 (bestp)： endl; coutKnapsack(p,w,c,n)endl;couts 重新开始 endl; coutq 退出 k;class Knap;class Object;class Objectfriend int Knapsack(int *,int *,int ,int ,int *); public:int operator = a.d);private: int ID; float d;/ 单位重量价值;class bbnodefrien

43、d Knap; friend int Kanpsack(int *,int *,int ,int ,int *);private: bbnode * parent;/ 指向父节点的指针 bool LChild;/左儿子结点标志;class HeapNode friend Knap;public: operator int () const return uprofit; void Insert(HeapNode N); void DeleteMax(HeapNode N);private:int uprofit, /结点的价值上界 profit;/结点所对应的价值int weight; /结点所对应的重量 int level;/ 活结点在子集树中所处的层序号bbnode * ptr; / 指向活结点在子集树中相应结点的指针 ;void HeapNode:Insert(HeapNode N)void HeapNode:DeleteMax(HeapNode N)class Knapfriend int Knapsack(int *,int