a.cpp

0-1背包问题

#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;
}