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

物品个数n=4，背包容量c=7，价值向量p={9 ，10，7,4}，重量向量w={3,5,2,1}请求出最优的解及其目标函数值。

#include

#include

#define  MaxSize 100       //最多结点数

typedef  struct  QNode

{    

    float  weight;

    float  value;

    int    ceng;

    struct  QNode *parent;

    bool leftChild;

}QNode,*qnode;             //存放每个结点

typedef struct 

{ 

    qnode  Q[MaxSize]; 

    int front,rear;

}SqQueue;          //存放结点的队列

SqQueue  sq;

float bestv=0; //最优解

int n=0;                      //实际物品数

float w[MaxSize];           //物品的重量

float v[MaxSize];            //物品的价值

int bestx[MaxSize];          // 存放最优解

qnode bestE;

void InitQueue(SqQueue &sq ) //队列初始化

{

    sq.front=1;

    sq.rear=1;

}

bool QueueEmpty(SqQueue sq) //队列是否为空

{

    if(sq.front==sq.rear)

        return true;

    else 

        return false;

}

void EnQueue(SqQueue &sq,qnode b)//入队

{

    if(sq.front==(sq.rear+1)%MaxSize)

    {

        printf("队列已满!");

        return ;

    }

    sq.Q[sq.rear]=b;

    sq.rear=(sq.rear+1)%MaxSize;

}

qnode DeQueue(SqQueue &sq)//出队

{

    qnode e;

    if(sq.front==sq.rear)

    {

        printf("队列已空!");

        return 0;

    }

    e=sq.Q[sq.front];

    sq.front=(sq.front+1)%MaxSize;

    return e;

}

void  EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild)

{

    qnode b;

    if (i==n)      //可行叶子结点

    {

        if (vt==bestv)

        {

            bestE=parent;

            bestx[n]=(leftchild)?1:0;

        }

        return;

    }

    b=(qnode)malloc(sizeof(QNode));   //非叶子结点

b->weight=wt;

b->value=vt;

b->ceng=i;

b->parent=parent;

b->leftChild=leftchild;

    EnQueue(sq,b);

} 

void  maxLoading(float w[],float v[],int c)

{ 

    float wt=0;

    float vt=0;

    int i=1;      //当前的扩展结点所在的层

    float ew=0;      //扩展节点所相应的当前载重量

    float ev=0;       //扩展结点所相应的价值

    qnode e=NULL;

    qnode t=NULL;

    InitQueue(sq);

    EnQueue(sq,t);       //空标志进队列

    while (!QueueEmpty(sq))

    {  

        wt=ew+w[i]; 

        vt=ev+v[i];

     if (wt <= c)

        {

         if(vt>bestv)

                bestv=vt;

            EnQueue1(wt,vt,i,e,true);   // 左儿子结点进队列

        }   

        EnQueue1(ew,ev,i,e,false);        //右儿子总是可行；

        e=DeQueue(sq);         // 取下一扩展结点

        if (e == NULL)

        {

            if (QueueEmpty(sq))   break;

            EnQueue(sq,NULL);        // 同层结点尾部标志

            e=DeQueue(sq);      // 取下一扩展结点

            i++;

        }

     ew=e->weight; //更新当前扩展结点的值

     ev=e->value;

    }

    printf("最优取法为：\\n");

for( int j=n-1;j>0;j--) //构造最优解

    {

     bestx[j]=(bestE->leftChild?1:0);

     bestE=bestE->parent;

    }

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

    {

        if(bestx[k]==1)

            printf("\\n物品%d:重量：%.1f，价值：%.1f\\n",k,w[k],v[k]);

    }

    printf("\\n");

    printf("最优价值为：%.1f\\n\\n",bestv);

}

void main()

{

    int c;

    float ewv[MaxSize];

printf("510专区\\n");

printf("请输入物品的数量：\\n");

    scanf("%d",&n);

    printf("请输入背包容量：\\n");

    scanf("%d",&c);

    printf("\\n请输入物品价值和重量:\\n\\n");

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

    {

        printf("物品%d:",i);

        scanf("%f%f",&ewv[i],&w[i]);

        v[i]=w[i]*ewv[i];

        printf("\\n");

    }

}

实验结果：    

    maxLoading(w, v, c);