loading.txt

装载问题的 适合于算法分析用的 做实验的哈

#include<iostream.h>   
class   loading   
{   
friend   int   maxloading(int   [],int,int,int   *);   
public:   
void   Backtrack(int   i);   
int   n;   
int   *w;   
int   c;   
int   *x;   
int   cw;   
int   bestw;   
};   
   void   loading::Backtrack(int   i)   
{   
          if   (i   >   n)   
          {   
                  if   (cw   >   bestw)   
                  {   
                          bestw   =   cw;   
                  }   
                  return;     //<---------------   
          }   
    
          if   (cw   +   w[i]   <=   c)   
          {   
                  x[i]=1;   
                  cw   +=   w[i];   
                  Backtrack(i   +   1);   
                  cw   -=   w[i];   
          }   
    
          Backtrack(i   +   1);   
          x[i]   =   0;   
}
   
int   maxloading(int   mu[],int   c,int   n,int   *mx)   
{   
loading   x;   
x.w=mu;   
x.x=mx;   
x.c=c;   
x.n=n;   
x.bestw=0;   
x.cw=0;   
x.Backtrack(1);   
return   x.bestw;   
} 
  

void   main()   
{   
int   n,c,k;   
int   *w,*x;   
cout<<"input   n\n";   
cin>>n;   
cout<<"input   c\n";   
cin>>c;   
w=new   int   [n+1];   
x=new   int   [n+1];   
cout<<"input   n   goods   \n";   
for(int   i=1;i<=n;i++)   
cin>>w[i];   
          k=maxloading(w,c,n,x);   
cout<<k;   
delete   w;   
delete   x;   
}