リュックサック問題のアルゴリズム

// BackPack.cpp : Defines the entry point for the console application.
//         
//       
/*
   ：   
   ：2001 10 12 (18:02:38-18:12:00)
   ：         
   ：2001 10 9 (14:00:00-15:00:00)
   ：  “  ”         
 ===================================================
     :
     n*n      n            “  ”,
             .(      ,       、 
       4       ,  ,        、   
              <      >)
     :
     :
 try(i,tw,tv)
 i:     
 tw:                
 tv:              
 {
  //    i            
  if(    i     )
  {
      i        (    i     );
   if(i<n-1)
    try(i+1,tw+  i   ,tv);
   else
    //       ,          ,        
                
       i     ;
  }
  //    i             
  if(     i      )
  {
   if(i<n-1)
    try(i+1,tw,tv-  i   );
   else
    //       ,          ,        
                
  }
 }
*/
#define N 100
int limitW,  //      
 totalV,  //        
 maxV;  //          
int option[N], //      
 curoption[N]; //        
struct Goods  //      
{
 int weight;
 int value;
};
Goods array[N];
int n;  //    
//     
// i:     
// tw:                
// tv:              
void Find(int i,int tw,int tv)
{
 int k;
 //    i            
 if(tw+array[i].weight <= limitW)
 {//    i     
  curoption[i] = 1; //   i        (    i     );
  if(i<n-1)
   Find(i+1,tw+array[i].weight,tv);
  else
  {//       ,          ,        
   for(k=0;k<n;k++) //             
    option[k] = curoption[k];
   maxV = tv;
  }
  curoption[i] = 0; //    i     
 }
 //    i             
 if(tv-array[i].value > maxV)
 {
  if(i<n-1)
   Find(i+1,tw,tv-array[i].value);
  else
  {//       ,          ,        
   for(k=0;k<n;k++) //             
    option[k] = curoption[k];
   maxV = tv-array[i].value;
  }
 }
}
void BackPack_Problem()
{
 int k,w,v;
 printf("      /n");
 scanf("%d",&n);
 printf("           /n");
 for(totalV = 0,k=0;k<n;k++)
 {
  scanf("%d%d",&w,&v);
  array[k].weight = w;
  array[k].value  = v;
  totalV += v;
 }
 printf("       /n");
 scanf("%d",&limitW);
 maxV = 0;
 for(k=0;k<n;k++)
  curoption[k] = 0;
 Find(0,0,totalV);
 for(k=0;k<n;k++)
  if(option[k])
   printf("%4d",k+1);
 printf("    = %d/n",maxV);
 printf("/n/n        ....../n");
}