洛谷P1460 健康的荷斯坦奶牛

解题思路：
首先想到的是搜索，搜索使用哪几种符合条件的饲料，找最小的花费。由于dfs的特点，先找到的方案一定是字典序最小的。
但是暴力搜索会超时，需要剪枝，详见注释

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,v[35],a[35][35],ans=1e9,cnt,t,c[35],top[35];
void dfs(int x,int sum){
    bool flag=0;
    for (int i=1;i<=n;i++) if (v[i]>0) {flag=1;break;}//边界条件，要使每个v[i]都<0；
    if (!flag){
        if (sum<ans){//最优性剪枝
            ans=sum;
            t=cnt;
            for (int i=1;i<=cnt;i++)
            c[i]=top[i];
        }
        return ;
    }
    for (int i=x+1;i<=m;i++){//从x+1搜索，不再搜索前边的，可行性剪枝
      for (int j=1;j<=n;j++)
       v[j]-=a[i][j];
        top[++cnt]=i;
        dfs(i,sum+1);
        --cnt;//回溯
        for (int j=1;j<=n;j++)
        v[j]+=a[i][j];//回溯 
      }
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++)
    scanf("%d",&v[i]);
    cin>>m;
    for(int i=1;i<=m;i++) 
    for (int j=1;j<=n;j++)
    scanf("%d",&a[i][j]);
    dfs(0,0);
    cout<<t<<" "; 
    for (int i=1;i<=t;i++)
    cout<<c[i]<<" "; 
    return 0;
} 

最后

以上就是美丽帅哥为你收集整理的洛谷P1460 健康的荷斯坦奶牛的全部内容，希望文章能够帮你解决洛谷P1460 健康的荷斯坦奶牛所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。