分支限界法-01背包问题

用分支限界法解决0-1背包问题

#include<iostream>
#include<stack>
#define N 200
using namespace std;
class HeapNode
{
public:
double uprofit,profit,weight;
int level,x[N];
};

stack<HeapNode> H;
double w[N],p[N];
double cw,cp,c;
int n;

double Bound(int i)
{
double cleft=c-cw,b=cp;
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
if(i<=n) b+=p[i]/w[i]*cleft;
return b;
}

void AddLiveNode(double up,double cp,double cw,bool ch,int level)
{
HeapNode nod;
nod.uprofit=up;
nod.profit=cp;
nod.weight=cw;
nod.level=level;
if(level<=n) H.push(nod);
}

double Knap()
{
int i=1;
cw=cp=0;
double bestp=0,up=Bound(1);
while(1)
{cout<<"down: "<<bestp<<endl<<"up: "<<up<<endl;
double wt=cw+w[i];
if(wt<=c)
{
if(cp+p[i]>bestp) bestp=cp+p[i];
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);
if(H.empty()) return bestp;

HeapNode node=H.top();
H.pop();
cw=node.weight;
cp=node.profit;
up=node.uprofit;
i=node.level;
}

}
int main()
{
cout<<"请输入n和c:"; cin>>n>>c;
cout<<"请输入w[i]"<<endl;
for(int i=1;i<=n;i++) cin>>w[i];

cout<<"请输
入p[i]"<<endl;
for(int i=1;i<=n;i++) cin>>p[i];

cout<<"最优值是："<<Knap()<<endl;
return 0;
}