回溯法背包问题.doc

回溯法背包问题.txt男人的承诺就像80岁老太太的牙齿，很少有真的。你嗜烟成性的时候，只有三种人会高兴，医生 你的仇人和卖香烟的。 #include<iostream>
#include <algorithm>

using namespace std;

class Knap
{
friend int Knaspack(int *,int *,int ,int );

public :
int Bound(int i);
void Backtrack(int i);

int c;//背包数量
int n;//物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最有价值
};

void Knap::Backtrack(int i)
{
if(i>n){
bestp=cp;
return ;
}
if(cw+w[i]<=c)
{
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)
Backtrack(i+1);
}
int Knap::Bound(int i)
{
int cleft=c-cw;
int b=cp;
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
if(i<=n)
b+=p[i]*cleft/w[i];
return b;
}

class Object{
friend int Knaspack(int *,int *,int ,int );
public:
int operator<=(Object a)const
{return (d>=a.d);}

int ID;
float d;
};

int Knapsack(int p[],int w[],int c,int n){
int W=0;
int P=0;

Object * Q=new Object[n];
for(int i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;
//sort(&Q,&Q+n-1);//两个参数分别为待排序数组的首地址和尾地址

float f;
for(i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p=new int [n+1];
K.w=new int [n+1];
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}

K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
K.Backtrack(1);

delete[] Q;
delete[] K.w;
delete[] K.p;
return K.bestp;
}

void main(){

int *p,*w,c,n;
cout<<"请输入物品数:";
cin>>n;
cout<<"请输入背包数量:";
cin>>c;

w=new int [n+1];
w[0]=0;
cout<<"请输入物品重量:";
for(int i=1;i<=n;i++)
cin>>w[i];

p=new int [n+1];
p[0]=0;
cout<<"请输入物品价值:";
for( i=1;i<=n;i++)
cin>>p[i];

cout<<"最优值:"<<Knapsack(p,w,c,n)<<endl;
}