分枝限界法解0-1背包问题

class Knap;

class Object;

class Object

{

    friend int Knapsack(int *,int *,int ,int ,int *);

public:

int operator <=(Object a)const

    {

     return (d >= a.d);

    }

private:

    int ID;

    float d;//单位重量价值

};

class bbnode

{

    friend 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 Knap

{

    friend int Knapsack(int *,int *,int ,int ,int *);

public:

    int MaxKnapsack();

private:

    HeapNode *H;

    int MaxBoundary(int i);

    void AddLiveNode(int up,int cp,int cw,bool ch,int level);

    bbnode * E;      //指向扩展结点的指针

    int c;           //背包容量

    int n;           //物品总数

    int *w;          //物品重量数组

    int *p;          //物品价值数组

    int cw;          //当前背包重量

    int cp;          //当前背包价值

    int * bestx;     //最优解的记录数组

};

//计算所相应的价值的上界

int Knap::MaxBoundary(int i)

{

    int cleft=c-cw;   //剩余容量

    int 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 Knap::AddLiveNode(int up,int cp,int cw,bool ch,int lev)

{

    //将一个新的活结点插入到子集树和最大堆H中

    bbnode * b=new bbnode;

b->parent=E;

b->LChild=ch;

    HeapNode N;

    N.uprofit=up;

    N.profit=cp;

    N.weight=cw;

    N.level=lev;

    N.ptr=b;

H->Insert(N);

}

//实施对子集树的优先队列式分支界限搜索

int Knap::MaxKnapsack()

{//优先队列式分支界限法，返回最大值，bestx返回最优解

    //定义最大堆的容量为1000

    H=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+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=MaxBoundary(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(int j=n;j>0;j--)

    {

     bestx[j]=E->LChild;

     E=E->parent;

    }

    return cp;

}

//对数据进行预处理并完成调用MaxKnapsack

int Knapsack(int p[],int w[],int c,int n,int bestx[])

{//返回最大值，bestx返回最优解

    //初始化

    int W=0;   //装包物品重量

    int P=0;   //装包物品价值

    //定义依单位重量价值排序的物品数组

    Object * Q=new Object[n];

for(int i=1;i<=n;i++)

    {

        //单位重量价值数组

        Q[i-1].ID=i;

        Q[i-1].d=(float)1.0*p[i]/w[i];

        P+=p[i];

        W+=w[i];

    }

if(W<=c) return P;//所有物品装包

    //依单位重量价值排序

    float f;

for( i=0;i     for(int j=i;j        {

         if(Q[i].d            {

                f=Q[i].d;

                Q[i].d=Q[j].d;

                Q[j].d=f;

            }

        }

    //创建类Knap的数据成员

    Knap K;

    K.p=new int [n+1];

    K.w=new int [n+1];

for(i=1;i<=n;i++)

    {

        K.p[i]=p[Q[i-1].ID];

        K.w[i]=w[Q[i-1].ID];

    }

    K.cp=0;

    K.cw=0;

    K.c=c;

    K.n=n;

    //调用MaxKnapsack求问题的最优解

    int bestp=K.MaxKnapsack();

for(int j=1;j<=n;j++)

        bestx[Q[j-1].ID]=K.bestx[j];

    delete []Q;

    delete []K.w;

    delete []K.p;

    delete []K.bestx;

    return bestp;

}

void main()

{

    int m,n;

    int i=0,j=0;

    int p[100],w[20],x[20];

    while(1)

    {

     cout<<"0-1背包问题——递归法"< cout<<"请输入背包的容量（m）和物品个数（n）："< cin>>m>>n;

cout<<"请输入每个物品的重量（w）和物品的价值（p）："< for(i=1;i<=n;i++)

     cin>>w[i]>>p[i];

cout<<"背包的最优解为:"< cout<<"最优解条件下选择的背包为:"< for(i=1;i<=n;i++)

     cout< cout<    }

}