#include <iostream.h>
#define N 8//物品的个数
float bestp=0;//最优装载总价值
float cw=0;//当前装载的总质量
float cp=0;//当前装载的总价值
float bestw=0;
int x[N];
int y[N];
float p[]={20,55,35,33,43,78,55,90};
float w[]={3,9,21,23,33,43,45,55};
float M=100;
void my_sort(float w[],float p[],int n)
{//排序w,p
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if((p[j]/w[j])>(p[i]/w[i]))
{
p[i]=p[i]+p[j];
p[j]=p[i]-p[j];
p[i]=p[i]-p[j];
w[i]=w[i]+w[j];
w[j]=w[i]-w[j];
w[i]=w[i]-w[j];
}
}
}
}
void backtrack(int n)
{
if(n>=N)
{
if(cp>bestp)
{
bestp=cp;
bestw=cw;
for(int j=0;j<N;j++)
{
y[j]=x[j];
}
}
return ;
}
for(int i=0;i<=1;i++)
{
if(i==0)
{
x[n]=0;
backtrack(n+1);
}
if(i==1&&cw+w[n]<=M)
{
cw+=w[n];
cp+=p[n];
x[n]=1;
backtrack(n+1);
cw-=w[n]*x[n];
cp-=p[n]*x[n];
}
}
}
void btknapsack(float w[],float p[],float M,int n,int x[])
{
for(int i=0;i<N;i++)
{
cp+=p[i];
cw+=w[i];
}
if(cw<=M)
{
bestp=cp;
bestw=cw;
for(int j=0;j<N;j++)
{
y[j]=1;
}
return ;
}
my_sort(w,p,n);
cp=cw=0;
backtrack(0);
}
int main()
{
btknapsack(w,p,M,N,x);
cout<<"背包可装入物质的总质量为:"<<M<<endl;
cout<<"装入背包的总价值p:"<<bestp<<endl;
cout<<"装入背包的物质总质量w:"<<bestw<<endl<<endl;
cout<<"装入的物质分别为:"<<endl;
for(int i=0;i<N;i++)
{
if(y[i])
{
cout<<"价值:"<<p[i]<<"\t"<<"质量:"<<w[i]<<"\t"<<endl;
}
}
cout<<endl;
return 0;
}