即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Healthy Holsteins 健康的好斯坦奶牛

编程语言 longlong_long 28℃ 0评论

题目如下:


农民JOHN以拥有世界上最健康的奶牛为骄傲。他知道每种饲料中所包含的的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛,以保持他们的健康,使喂给牛的饲料的种数最少。给出牛所需的最低的维他命,输出喂给牛需要哪些种类的饲料?


给出牛所需的最低的维他命量,输出喂给牛需要哪些种类的饲料,且所需的饲料剂量最少。


维他命量以整数表示,每种饲料最多只能对牛使用一次,数据保证存在解。


INPUT FORMAT


第1 行:一个整数V(1<=V<=25),表示需要的维他命的种类数。


第2 行:V个整数(1<=每个数<=1000),表示牛每天需要的维他命的最小量。


第3 行:一个整数G(1<=G<=15),表示可用来喂牛的饲料的数量。下面G行,第i行表示编号为i饲料包含的各种维他命的量的多少。


SAMPLE INPUT (file holstein.in)


4


100 200 300 400


3


50 50 50 50


200 300 200 300


900 150 389 399


OUTPUT FORMAT


输出文件只有一行,包括:


牛必需的最小的饲料种数P


后面有P个数,表示所选择的饲料编号(按从小到大排列)。


SAMPLE OUTPUT (file holstein.out)


2 1 3

这一道题第一眼看起来认为书是动态规划,其实一个dfs就可以解决


代码如下:

#include
#include
#include
#include
using namespace std;
int a[26][26],b[26];
int bj[26],js=2147483,ko=1,n,m;
char s[100],l[100];
int pd() { 
    for(int i=1; i<=n; i++)
        if(bj[i]//判断是不是维生素大于牛所需的最低的维他命 
            return 0;//如果不是返回0 
    return 1;//如果是返回1 
}
void dfs(int k,int ans) {
    if(pd()==1) {//如果 维生素大于牛所需的最低的维他命 
        if(js>ans) {//如果当前最小值大于本次的值 
            for(int i=1; i<=m; i++)
                l[i]=s[i];//把s数组的值赋给l数组 
        }
        js=min(js,ans);//取js和ans中的最小值 
        return ;//返回 
    }
    for(int i=k+1; i<=m; i++) {
        for(int j=1; j<=n; j++)
            bj[j]+=a[i][j];
        s[i]='1';//表记i说明i点别被选过 
        dfs(i,ans+1);//搜索 
        for(int j=1; j<=n; j++)
            bj[j]=bj[j]-a[i][j];
        s[i]='0';//讲i的表记清空 
    }
}
int main() {
    cin>>n;//输入 
    for(int i=1; i<=n; i++)
        cin>>b[i];
    cin>>m;
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            cin>>a[i][j];
    for(int ii=1; ii<=m; ii++) {
        memset(s,0,sizeof(s));//把s数组的值清空 
        s[ii]='1';//表记ii 
        memset(bj,0,sizeof(bj));//把bj数组清空 
        for(int j=1; j<=n; j++)
            bj[j]=a[ii][j]; 
        dfs(ii,1);//搜索 
    }
    cout<" ";
    for(int i=1; i<=m; i++) {
        if(l[i]=='1')//如果点i被标记过 
            cout<" ";//输出 
    }
    return 0;
}

转载请注明:CodingBlog » Healthy Holsteins 健康的好斯坦奶牛

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情