我就是把每个customer需要的features顺着搜一遍,当然重复的不用搜 
代码写的很烂^^ 
测试数据对了 
#include <iostream.h> 
#include <stdlib.h> 

int minc,maxc,n,m; 
int cost[21]; 
int customer[21][22]; 
int caseno,i,j,k,s,t; 
int sales,costs,margin,feat[21],cust[21],consider[21]; 
int tempcust[21]; 
double PI; 
    
int compare(const void*a,const void *b) 
{ 
    int x=*((int *)a),y=*((int *)b); 
    if (x==y) return 0; 
    if (x<y) return -1; 
    else return 1; 
} 
    
int main() 
{ 

   cout.precision(3); 
   cout.setf(ios::fixed,ios::floatfield); 
    
   cin>>caseno; 
   for (int i=0;i<caseno;i++) 
   { 
       cin>>minc>>maxc>>n>>m; 
       for (j=1;j<=n;j++) 
           cin>>cost[j]; 
       for (j=1;j<=m;j++) 
       { 
           int num; 
           cin>>num; 
           customer[j][0]=num; 
           for (k=1;k<num+2;k++) 
               cin>>customer[j][k]; 
       } 
       for (j=1;j<=m;j++) 
       qsort(customer[j]+1,customer[j][0],sizeof(int),compare); 
        
       margin=0; 
       PI=0; 
        
       for (j=1;j<m;j++)  
           consider[j]=0; 
    
       for (j=1;j<=m;j++) 
       { 
           if (consider[j]) break; 
            
           int tsales,tcosts=0; 
           consider[j]=1; 
            
           for (k=1;k<=customer[j][0];k++) 
                tcosts+=cost[customer[j][k]]; 
           if (tcosts<minc || tcosts>maxc) break; 
            
           for (k=0;k<21;k++) tempcust[k]=0; 
           tempcust[j]++; 
           tempcust[0]++; 
        
           k=customer[j][0]+1; 
           tsales=customer[j][k];     
           for (s=1;s<=m;s++) 
           { 
               if (s==j) continue; 
               if (customer[s][0]>customer[j][0]) continue; 
                
               k=1; 
               int count=0; 
               for (t=1;t<=customer[s][0];t++) 
               { 
                   for (;k<=customer[j][0];k++) 
                       if (customer[s][t]==customer[j][k]) 
                       { 
                         count++;  
                         break; 
                       } 
                   if (k>customer[j][0]) break; 
               } 
               if (count<customer[s][0]) continue; 
                
               tempcust[0]++; 
               tempcust[s]++; 
               if (count==customer[j][0]) consider[s]=1; 
               tsales+=customer[s][count+1]; 
           } 
            
           double temp=(double)tsales/tcosts; 
           if (temp>PI)  
                      { 
                        sales=tsales; 
                        costs=tcosts; 
                        PI=temp; 
                        margin=tsales-tcosts; 
                        feat[0]=customer[j][0]; 
                        for (k=1;k<=feat[0];k++) feat[k]=customer[j][k]; 
                        for (k=0;k<21;k++) cust[k]=tempcust[k]; 
                       } 

           else if (temp==PI) 
           { 
                int temp1=tsales-tcosts; 
                if (temp1>margin) 
                       { 
                        sales=tsales; 
                        costs=tcosts; 
                        PI=temp; 
                        margin=temp1; 
                        feat[0]=customer[j][0]; 
                        for (k=1;k<=feat[0];k++) feat[k]=customer[j][k]; 
                        for (k=0;k<21;k++) cust[k]=tempcust[k]; 
                       } 

                else if (temp1==margin) 
                { 
                     if (customer[j][0]<feat[0]) 
                     { 
                        sales=tsales; 
                        costs=tcosts; 
                        PI=temp; 
                        margin=temp1; 
                        feat[0]=customer[j][0]; 
                        for (k=1;k<=feat[0];k++) feat[k]=customer[j][k]; 
                        for (k=0;k<21;k++) cust[k]=tempcust[k]; 
                       } 

                     else if (customer[j][0]==feat[0]) 
                     { 
                          if (tempcust[0]>cust[0]) 
                          { 
                        sales=tsales; 
                        costs=tcosts; 
                        PI=temp; 
                        margin=temp1; 
                        feat[0]=customer[j][0]; 
                        for (k=1;k<=feat[0];k++) feat[k]=customer[j][k]; 
                        for (k=0;k<21;k++) cust[k]=tempcust[k]; 
                       } 

                     } 
                } 
           } 
       } 
       cout<<"Feature Set "<<i+1<<endl<<PI<<endl<<sales<<endl<<costs<<endl; 
       for (j=1;j<=feat[0];j++) cout<<feat[j]<<' '; 
       cout<<endl; 
       for (j=1;j<21;j++)  
           if (cust[j]) cout<<j<<' '; 
       cout<<endl; 
   } 
   return 0; 
}