#include
//头文件
using namespace std;//空间命名。
int f,nfeed[30],type,t[30][30],m=20,mx[30],ans[30];//定义
bool cz(int x)
{
for(int i=1;i<=f;i++)
{
int he=0; //别忘了初始化！！！
for(int j=1;j<=x;j++)
{
he+=t[ans[j]][i];//累加
}
if(he<nfeed[i]) return false;//一旦没喂饱就赶紧跳的
}
return true;//喂饱了。
}
void dfs(int pos,int z)
{
if(pos>type)//搜完了，不管它成功不成功我都要结束了，否则就会死循环。
{
if(cz(z) && z<m)//成功了
{
m=z;
for(int i=1;i<=z;i++)
{
mx[i]=ans[i];//复制
}
}
return ;//快给我结束！
}
ans[z+1]=pos;
dfs(pos+1,z+1);//继续搜索
dfs(pos+1,z);//继续搜索
//是不是感觉很像动归！
}
int main()
{
cin>>f;//读入奶牛需要的维他命的种类数。
for(int i=1;i<=f;i++)
cin>>nfeed[i];//读入牛每天需要的每种维他命的最小量。
cin>>type;//读入可用来喂牛的饲料的种数。
for(int i=1;i<=type;i++)
{
for(int j=1;j<=f;j++)
{
cin>>t[i][j]; //饲料包含的各种维他命的量的多少。
}
}
dfs(1,0);//爆搜！
cout<<m<<' ';//输出
for(int i=1;i<=m;i++)
cout<<mx[i]<<' ';//输出
cout<<endl;//输出
return 0;
}
为什么 dfs 里面不用回溯写 ans[z+1]=0，说下过程内容：在这个问题中，ans 数组的每个元素都表示选取了哪些饲料，所以在搜索的过程中，我们只需要记录选取的饲料的编号即可，不需要回溯到上一个状态。因为在搜索的过程中，每次都是新选取一个饲料或者不选取当前饲料，不会出现回到之前选取的状态的情况。所以不需要回溯。
