题解 P1460 【健康的荷斯坦奶牛 Healthy Holsteins 】

· · 题解

这道题算是很简单的dfs，都不需要剪枝。

首先定义一个搜索函数，函数传递的变量为t和s,t表示搜索到了第t种饲料，s表示目前选的饲料的总数。

然后确定搜索的边界，也就是t>饲料的种数，然后判断每次选的那些饲料中的维生素之和是不是都大于等于牛每天需要的每种维他命的最小量（可以用个函数写）。如果是，就判断选的饲料的总数小于以前的最优解（类似于打擂台的那种操作），如果小于，那么当前最优解就要被替换掉，而最优解的一个数组也要被替换掉。最后return即可。

接着开始写函数的主体部分。首先我们选第t种饲料，那么s就要加一，并且我们还要把t存在一个数组当中（想想为什么要存）。然后就可以调用函数，即search(t+1,s+1); 调完函数后，记得要回溯.把t从数组中拿走。接下来我们不选第t种饲料，这样做很简单，直接搜索一步：search(t+1,s); 就行了。

最后输出解即可。

思路就这么多。

下面是代码部分。

请勿抄袭！！！

#include <bits/stdc++.h>//懒人最爱的万能头文件 
using namespace std;//名字空间 
int ans[1000];//这个数组是来存储解的。 
int a[1000];//表示牛每天需要的每种维他命的最小量。 
int b[1000][1000];//每种饲料包含的各种维他命的量的多少。
int c[1000];//每次搜索选的饲料编号 
int n,m,minn=100000000;
bool pd(int x)//这是判断每次选的那些饲料中的维生素之和是不是都大于等于牛每天需要的每种维他命的最小量的函数 
{
    for(int i=1; i<=n; i++)
    {
        int sum=0;
        for(int j=1; j<=x; j++)
        sum+=b[c[j]][i];//用一个sum累加 
        if(sum<a[i]) return false;//如果有一项维生素比牛需要的维生素要少，直接返回false 
    }
    return true;
}
void search(int t,int s)//搜索的函数 
{
    if(t>m)//边界
    {
        if(pd(s))//必须得满足条件
        {
            if(s<minn)//判断选的饲料的总数小于以前的最优解
            {
                minn=s;//替换掉
                for(int i=1; i<=minn; i++)
                {
                    ans[i]=c[i];//答案的数组也要被替换
                }
            }
        }
        return; //返回
    }
    c[s+1]=t;//把t放在数组里
    search(t+1,s+1);//搜索一步
    c[s+1]=0;//回溯一步
    search(t+1,s);//如果不选第t种饲料的操作
}
int main()//主函数部分
{
    cin>>n;//读入
    for(int i=1; i<=n; i++)
    cin>>a[i];//读入
    cin>>m;//读入
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        cin>>b[i][j];//还是读入
    }
    search(1,0);//调用搜索函数
    cout<<minn<<' ';//输出
    for(int i=1; i<=minn; i++)
    cout<<ans[i]<<' ';//还是输出
    return 0;//结束程序
}