0-1バックパックの問題(分岐限界-通常キュー)

2421 ワード

//Author: FF-W
//Date: 29, Oct, 2018
//Purpose:0-1    (    -    )

#include 
#include
using namespace std;

class itemNode
{
public:

    int cw;
    int cp;
    bool isleft;
    int level;
    itemNode* parentNode;
    itemNode(int w,int p,bool is_left,int lev,itemNode*node)
    {
        cw=w;
        cp=p;
        isleft=is_left;
        level=lev;
        parentNode=node;
    }
    itemNode()
    {

    }

    /*itemNode(itemNode* node)
    {
        cw=node->cw;
        cp=node->cp;
        isleft=node->isleft;
        level=node->level;
       // parentNode=node->parentNode;
    }*/

    itemNode& operator=(const itemNode& node)
    {
        cp=node.cp;
        cw=node.cw;
        isleft=node.isleft;
        level=node.level;
        parentNode=node.parentNode;
        return *this;

    }

    itemNode* clone()
    {
        return this;
    }

};
queueitemQueue;

bool check(int t,int cp,int V[],int nItem,int bestcp)
{

    int vSum=0;
    for(int i=t; ibestcp)
        return true;
    return false;
}

itemNode* branch_bounding(int nItem,int W[],int V[],int wAll)
{
    int i=0;
    int cp=0;
    int cw=0;
    int bestcp=0;
    itemNode *node=NULL;
    itemNode *retNode=NULL;

    while(true)
    {

        if(i+1>nItem&&node->cp>bestcp)
        {
            retNode=node->clone();
            bestcp=node->cp;
        }

        else
        {
            if(cw+W[i]<=wAll)
            {
                itemQueue.push(new itemNode(cw+W[i],cp+V[i],true,i+1,node));
            }
            if(check(i+1,cp,V,nItem,bestcp))
            {
                itemQueue.push(new itemNode(cw,cp,false,i+1,node));

            }
        }

        if (itemQueue.empty())
        {
            break;
        }
        node=itemQueue.front();
        itemQueue.pop();
        i=node->level;
        cw=node->cw;
        cp=node->cp;
    }
    return retNode;
}

void show(itemNode*node)
{
    while(node!=NULL)
    {
        if(node->isleft!=0)
        {
            cout<level<parentNode;
    }
}


int main()
{
    itemNode *resNode=NULL;
    cout<>wAll;
    cout<>nItem;
    int W[nItem];
    int V[nItem];
    cout<>V[i]>>W[i];
    }
    resNode=branch_bounding(nItem,W,V,wAll);
    cout<