计蒜客强迫症的吃货（dfs+枚举）

缺乏、安全感 2024-02-17 22:14 183阅读 0赞

晓萌作为一个营养学专家，吃东西的时候总是要考虑是否能满足他的各种营养物质需求，大家都说他是一个有强迫症的吃货。晓萌知道每种食品中营养物质的含量，请你帮他安排食谱，以保持他获得所需营养物质的同时，吃的食品的种类最少。（营养物质含量为整数，每种食品晓萌只吃一次）。

输入第1行为一个整数V表示晓萌需要的营养物质的种类数（1≤V≤25）。

输入第2行包括用空格分隔开的V个整数，依次表示每种营养物质的需求量（1≤每个整数≤1000）。

输入第3行包括一个整数G表示提供可以给晓萌吃的食品的种类数（1≤G≤15）。

接下来的G行，每行包括用空格分隔开的V个整数，G行中的第i行中V个整数依次表示第i种食品中每种营养物质的需求量（1≤每个整数≤1000）。

输出包括空格分隔的多个数，第一个数为必需的最小的食品种数P；后面有P个数，表示所选择的食品编号（按从小到大排列）；如果有多个解，输出食品序号最小的（即字典序最小）。

##### 样例输入 #####

4
    100 200 300 400
    3
    50 50 50 50
    200 300 200 300
    900 150 389 399

##### 样例输出 #####

2 1 3

分析：枚举+dfs求解，分别枚举食品总数为1、2、3、……、p，直到找到满足条件的即可打印输出。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<vector>
    using namespace std;
    const int maxn=15+2;
    vector<int>g[maxn];
    int path[maxn];
    int V,G;
    int N;
    int flag;
    
    void dfs(int cur,int cnt){
    	path[cnt]=cur;
    	if(cnt>N || flag || cur>G)return ;
        
        if(cnt==N){
    	vector<int>vec=g[path[1]];
    	for(int i=2;i<=N;i++){
    	      for(int j=0;j<vec.size();j++){
    	      	vec[j]+=g[path[i]][j];
    		  } 
    	}
    	
    	int f=0;
    	for(int i=0;i<vec.size();i++){
    		if(g[0][i]>vec[i]){
    			f=1;
    			break;
    		}
    	}
    	if(!f){
    		flag=1;
    		printf("%d",cnt);
    		for(int i=1;i<=cnt;i++)
    		printf(" %d",path[i]);
    		printf("\n");
    		return ;
    	}
    }
    
        for(int j=cur+1;j<=G;j++){
    	   dfs(j,cnt+1);
    	}
    	
    	dfs(cur+1,cnt);	
    }
    
    int main(){
        while(scanf("%d",&V)==1){
        	for(int i=0;i<V;i++){
        		int t;
        		scanf("%d",&t);
        		g[0].push_back(t);
    		}
    		
    		scanf("%d",&G);
    		for(int i=1;i<=G;i++){
    			for(int j=0;j<V;j++){
    				int t;
    				scanf("%d",&t);
    				g[i].push_back(t);
    			}
    		}
    		
    		flag=0;
    		for(int i=1;i<=G;i++){
    			if(flag)break;
    			N=i;   //枚举 
    			dfs(1,1);
    		}
    		
    		for(int i=0;i<maxn;i++)g[i].clear();
    	}	
    	return 0;
    }