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<