優先キュー式分岐限界法0-1リュックサック
#include<iostream>
#include <algorithm>
#include "heap.h"
using namespace std;
class Knap
{
public:
Knap(double *pp,double *ww,double cc,int nn)//
{
p=pp;
w=ww;
c=cc;
n=nn;
cw=0;
cp=0;
E=0;
bestx=new int[n+1];
H=init(100);
}
double knapsack();// 。
double Bound(int i);//
void AddLiveNode(double up,double cp,double cw,bool ch,int lev);
int MaxKnapsack();
void output()//
{
for(int i=1;i<=n;i++)
cout<<bestx[i]<<" ";
cout<<endl;
}
private:
double c; //
int n; //
double *w; //
double *p; //
double cw; //
double cp; //
bbnode *E; //
int *bestx; //
HeapQueue H;
};
class Object
{
public:
int ID;
double d;
};
int cmp(Object a,Object b)// 。
{
return a.d>b.d;//
}
double Knap::Bound(int i)
{
Object *Q=new Object[n+1];
int j;
for(j=1;j<=n;j++)
{
Q[j].ID=j;
Q[j].d=1.0*p[j]/w[j];
}
sort(Q+1,Q+n+1,cmp);/* Q 。 cmp() 。 Q[1] Q */
/* Object , Bound() , , */
/*
for(j=1;j<=n;j++)
cout<<Q[j].ID<<" ";
cout<<endl;
*/
double cleft=c-cw;
double b=cp;
while(i<=n&&w[Q[i].ID]<=cleft)
{
cleft-=w[Q[i].ID];
b+=p[Q[i].ID];
i++;
}
if(i<=n)
b+=1.0*p[Q[i].ID]*cleft/w[Q[i].ID];/* , 。*/
return b;
}
double Knap::knapsack()
{
/* , , 。*/
int i;
double W=0;
double P=0;
for(i=1;i<=n;i++)
{
W+=w[i];
P+=p[i];
}
if(W<=c) // 。bestx[]=1;
{
for(int j=1;j<=n;j++)
bestx[j]=1;
return P;
}
/* , , 。*/
return MaxKnapsack();
}
void Knap::AddLiveNode(double up,double cp,double cw,bool ch,int lev)
{
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;
InsertMax(N,H);
}
int Knap::MaxKnapsack()
{
double bestp=0;//
double up=Bound(1);//
// cout<<up<<endl;// 22
int i=1;
while(i != n + 1)
{
//double wt=cw+w[i];
//cout<<wt<<endl;
if(cw+w[i]<=c)
{
if(cp+p[i]>bestp)/* cw+w[i]<=c, bestp*/
bestp=cp+p[i];
AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);//
}
up=Bound(i+1);
//
if(up>=bestp)
AddLiveNode(up,cp,cw,false,i+1);
//
HeapNode N;
N=DeleteMax(H);
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;
}
int main()
{
int n=4;
double c=7;//
/* , p[] w[] -100, 1 , 0 , -100 */
double p[]={-100,9,10,7,4};//
double w[]={-100,3,5,2,1};//
Knap k=Knap(p,w,c,n);
cout<<k.knapsack()<<endl;
k.output();
return 1;
}
</pre><pre class="cpp" name="code">
struct bbnode
{
bbnode *parent;
bool LChild;
};
struct HeapNode
{
bbnode *ptr; //
double weight; //
double uprofit, //
profit; //
int level; //
};
/****************************************************************************/
/****************************************************************************/
typedef HeapNode ElemType;
#define MaxData 32767
typedef struct Heap
{
int capacity;
int size;
HeapNode *Elem;
}Heap,*HeapQueue;
HeapQueue init(int maxElem)
{
HeapQueue H=new Heap;
H->capacity=maxElem;
H->size=0;
H->Elem=new HeapNode[maxElem+1];
H->Elem[0].uprofit=MaxData;
return H;
}
void InsertMax(ElemType x,HeapQueue H)
{
int i;
for(i=++H->size;H->Elem[i/2].uprofit<x.uprofit;i/=2)
H->Elem[i]=H->Elem[i/2];// i i/2
H->Elem[i]=x;
}
ElemType DeleteMax(HeapQueue H)
{
int i,child;
ElemType MaxElem,LastElem; // 。
MaxElem=H->Elem[1]; // 1 。
LastElem=H->Elem[ H->size-- ]; // size 。
for(i = 1 ; i * 2 <= H->size ; i = child)
{
child=i * 2;
/* , , ;
Child = H->Size , 。
*/
if(child != H->size && H->Elem[child+1].uprofit>H->Elem[child].uprofit)
child++;//
if(LastElem.uprofit < H->Elem[child].uprofit)
H->Elem[i]=H->Elem[child];
}
H->Elem[i]=LastElem;
return MaxElem;
}