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

根据我对算法书上的理解，自己瞎写出了以下代码，但是结果并不正确。不知具体哪里错了，还望大神指出。

先来说说我的理解吧。

分支界限法解决01背包问题：

1)   先求出每个物品的单位重量的价值，并按降序排序；

2)   按此顺序取物品，取或不取的时候都计算出上界：ub=cv+(bagw-cw)(value[i]/weight[i])，即（当前价值+最佳回报*剩余重量）；

3)   比较两种情况下的上界ub，选择界限大的方式。前提是选取该物品后总重不会超过背包容量：bagw；

4）一个物品要么选，要么不选，选了就往选了的方式下继续分支，重复2，3，没选就往没选的方式下分支。

但是在计算的过程中，我发现，只要选择的情况下不超过总重量bagw就不会不选它。

#include<stdio.h>

#include<iostream>

#include<queue>

using namespace std;

 

//bool select[10];//定义一个bool型数组用于判定是否选中对应物品；

int bagw=50,bagv,bestvalue,cw,cv;//背包可承受重量，背包可承受价值，最佳价值，当前重量，当前价值；

float ub;//上界;

//queue<thing> bestq;//定义一个结构体队列，用于存放最终结果；

struct avgvalue{//结构体存放物体的编号与单位重量的价值；

    int num;

    float avg;

    int value;//对应物品价值；

    int weight;//对应物品重量；

}re[10];

 

struct node{//定义结点；

    int cw;

    int cv;

    float ub;

}point[2];//point[0]表示左结点，[1]表示右结点；

 

void compare(avgvalue re[10])//排序物品单位重量的价值；

{

    int i,j,tmp;

    float t;

    for(i=0;i<=9;i++)

    {

       for(j=i+1;j<=9;j++)

        {

           if(re[i].avg<re[j].avg)

            {

               t=re[i].avg;

               re[i].avg=re[j].avg;

               re[j].avg=t;

               tmp=re[i].value;

               re[i].value=re[j].value;

               re[j].value=tmp;

               tmp=re[i].weight;

               re[i].weight=re[j].weight;

               re[j].weight=tmp;

            }

            else

               continue;

        }

    }

}

int der(avgvalue re1[10])//界限函数；

{

    int i,k,t;//j用来存放当前最大单位回报;

    float j;

    cw=0,cv=0;//初始化当前重量与价值；

    j=re[0].avg;

   ub=j*(bagw-cw)+cv;//上界公式,找到根节点；

    for(i=0;i<=8;i++)

    {

       j=re[i+1].avg;

       point[1].cv=cv;

       point[1].cw=cw;

        point[1].ub=j*(bagw-point[1].cw)+point[1].cv;//不包含第i个物品时当前最佳回报；

       point[0].cw=re1[i].weight;

       if(cw+point[0].cw<=bagw)//包含第i个物品不超重的情况下；

        {

           point[0].cv=re1[i].value;

           point[0].ub=j*(bagw-cw-point[0].cw)+point[0].cv+cv;//包含第i个物品时当前最佳回报；

 

           if(point[0].ub>point[1].ub)

            {

               ub=point[0].ub;

               cw+=point[0].cw;

               cv+=point[0].cv;

            }

            else

               ub=point[1].ub;

        }

        else//若包含超重，直接选择不包含的情况；

           ub=point[1].ub;

    }

    return cv;

}

 

int main()

{

    int i;

   for(i=0;i<=9;i++)

    {

       cin>>re[i].weight;//输入10个物品的重量；

    }

   for(i=0;i<=9;i++)

    {

       cin>>re[i].value;//输入10个物品的价值；

    }

    for(i=0;i<=9;i++)

    {

        re[i].num=i;

        re[i].avg=(float)re[i].value/re[i].weight;

    }

    compare(re);

   bestvalue=der(re);

   cout<<bestvalue<<endl;

    return 0;

}