题目描述

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using  namespace std;
const int N=1e3+10;
 
int niuneed[N];
int daily[N][N];
int v;
int st[N];
int g;
int min1=999999;
int ans[N];

bool check()
{  int sum[v+10]={0};
   for(int i=1;i<=v;i++)
       {  
           for(int j=1;j<=g;j++)
               {
                     if(st[j]==1)  //这个选择了的话
                       {
                           sum[i]+=daily[j][i];
                           
                       }

               }
           
            //cout<<sum[i]<<endl;

}
   
   for(int  i=1;i<=v;i++ )
            {
              if(sum[i]<niuneed[i])
                return  false;

            }  


     return true;       

}


void dfs(int t)
{    if(t>g)
       {  int now=0;
          for(int i=1;i<=g;i++)
             if(st[i]==1)  
                   {       now++;}
            if(check())
                 {    // cout<<"use:"<<now<<" now min1 is"<<min1<<endl;
                    
                    if(now<=min1)  // 如果出现了新的答案 
                       {    memset(ans,0,sizeof ans);  //！！！！！！这很重要 一定要清空之前选择的饲料种类！@！！！！！  因为出现了更好的
                           min1=now;
                           
                           for(int i=1;i<=g;i++)
                              {   
                                   if(st[i]==1)
                                   { ans[i]=1;
                                     
                                    }
                              }
                       
                       }
                  
                  
                 }       
                       

           
          return ;
       }

  st[t]=2;
  dfs(t+1);
  st[t]=0;


  st[t]=1;
  dfs(t+1);
  st[t]=0;




}

int main()
{  cin>>v;
   for(int i=1;i<=v;i++)
     {
         cin>>niuneed[i];
     }
   cin>>g;

    for(int i=1;i<=g;i++)
     for(int j=1;j<=v;j++)  
          {
              cin>>daily[i][j];
          }

   dfs(1);

  cout<<min1<<" ";

  for(int i=1;i<=g;i++)
     {
         if(ans[i]==1)
            cout<<i<<" ";
     }


   return 0;


}

思路

本质是一个指数型枚举(选还是不选?)，在到达了递归的终点之后。检验选了的饲料里面的n种成分是否可以满足要求，可以的话则将原先的ans初始化，之后在更新答案。

注意事项

当我们遍历完一种情况或者找到一种更好的情况，一定要记得将原来答案初始化！也就是恢复现场，这是搜索经常要注意的。