题目内容
下面是优先队列式分支限界算法解0-1背包问题的部分主代码,分析代码将【】内的代码补齐。TempleteTypepknap::MaxKnapsack(){//优先队列分支限界法,返回最大价值,最优解bestxH=newMaxHeap>(1000);//定义最大堆的容量为1000bestx=newint[n+1];inti=1;E=0; cw=cp=0;Typepbestp=0;Typepup=Bound(1);while(【1】){Typewwt=cw+w[i];if(wt<=c){ if(cp+p[i]>bestp) 【2】; AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=Bound(i+1);if(up>bestp)AddLiveNode(up,cp,cw,false,i+1);//从优先队列中取下一个扩展节点HeapNodeN;H->DeleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.upprofit;i=N.level;}//构造最优解for(intj=n;j>0;j--){bestx[j]=E->lchild; E=E->parent;}returncp;}
查看答案
搜索结果不匹配?点我反馈