P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins

题目描述

农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。

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

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

输入格式

第一行一个整数 v，表示需要的维他命的种类数。
第二行 vv* 个整数，表示牛每天需要的每种维他命的最小量。

第三行一个整数 g，表示可用来喂牛的饲料的种数。
下面 g 行，第 n 行表示编号为 n* 饲料包含的各种维他命的量的多少。

输出格式

输出文件只有一行，包括牛必需的最小的饲料种数 p；后面有 p 个数，表示所选择的饲料编号（按从小到大排列）。

如果有多个解，输出饲料序号最小的（即字典序最小）。

输入输出样例

输入 #1

1
2
3
4
5
6
4
100 200 300 400
3
50  50  50  50
200 300 200 300
900 150 389 399

输出 #1

1
2 1 3

注意几点：1、因为要字典序输出，对于一个饲料，要先搜索 “选择” 的状态，再搜索 “不选” 的。如果先选择 ”不选 “饲料的状态，dfs 回溯的时候会从后往前搜，不符合字典序。

2、数组需要撤销操作！

3、如果要用 bfs , 不要遗漏 “不选” 的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int MAX=25+10;
int u,t[MAX],g,ans=INF,rec;
int a[MAX][MAX],k[MAX];
bool judge(){
	fi(i,0,u)
		if(k[i] < t[i]) return false;
	return true;
}
void dfs(int ind,int cnt,int s){
	if(cnt > ans || cnt > g ||ind>g) return;
	if(judge() && ans > cnt) {
		ans = cnt; 
		rec = s;
		return;
	}
	fi(i,0,u) k[i] += a[ind][i];
	dfs(ind+1,cnt+1,s|(1<<ind)); //选 
	fi(i,0,u) k[i] -= a[ind][i];
	dfs(ind+1,cnt,s);//不选 
}
int main(){
	freopen("in","r",stdin);
	sf(u);
	fi(i,0,u) sf(t[i]); 
	sf(g);
	fi(i,0,g)
		fi(j,0,u) sf(a[i][j]);
	dfs(0,0,0);
	pf(ans);pfc(" ");
	int t=0;
	fi(i,0,g)
		if(rec & (1<<i)){
			pf(i+1);pfc(" ");
		}
	return 0;
}