#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[z+1] 存储的是第 z+1 个被选中的饲料的编号，而不是每个状态的选择情况。在 dfs 回溯时，搜索到下一层会覆盖掉上一层的选择，不需要回溯。而在搜索完一条完整的路径后，直接返回上一层即可，不需要清空 ans 数组。
