USACO Section 2.1 - Healthy Holsteins 二进制枚举

这道题写了很久~用了好多方法~~最开始想要先按长度再按从小到大输出~~就用BFS了~~结果给爆空间了~~后来想用多维背包~~结果不会搞~~最后才想到了其实数据量很小~~用BFS时我也不是超时而是爆空间~~其实每个物品就是选与不选两种状态~~分别用1,0表示再按顺序排成一个数就是一个二进制数!!并且这个二进制最多也就15位!!才几万!!

所以就从1开始枚举过去~~每次转化成二进制然后判断是不是符合要求~~再判断是不是更优~~

最后输出题目所要求的解就行了!!

Program:

/*  
ID: zzyzzy12  
LANG: C++  
TASK: holstein
*/    
#include<iostream>    
#include<stdio.h>    
#include<string.h>    
#include<math.h>    
#include<algorithm>    
#include<queue>
using namespace std;   
int v,g,a[31],i,j,s[31][31],p,k,num,ans[31],sum[31],m;
int t[31],tnum;
int main()
{
     freopen("holstein.in","r",stdin);
     freopen("holstein.out","w",stdout);  
     scanf("%d",&v);
     for (i=1;i<=v;i++) scanf("%d",&a[i]);
     scanf("%d",&g);
     for (i=1;i<=g;i++) 
        for (j=1;j<=v;j++) scanf("%d",&s[i][j]);
     p=(int)pow(2,g);
     num=100000;
     for (k=1;k<p;k++)  
     {
           tnum=0;
           i=k; j=0;
           memset(sum,0,sizeof(sum));
           while (i)
           {
                j++;
                if (i%2)
                {
                      for (m=1;m<=v;m++) sum[m]+=s[j][m];
                      t[++tnum]=j;        
                }
                i/=2;
           }
           for (m=1;m<=v;m++)
              if (sum[m]<a[m]) goto A;
           if (tnum<num)
           {
                 num=tnum;
                 for (m=1;m<=num;m++) ans[m]=t[m];        
           }else
           if (tnum==num)
           {
                 for (m=1;m<=num;m++)  
                     if (ans[m]<t[m]) goto A;
                 for (m=1;m<=num;m++) ans[m]=t[m];           
           } 
           A: ;
     }
     printf("%d",num);
     for (i=1;i<=num;i++) printf(" %d",ans[i]);
     printf("\n");
     return 0;   
}