当前位置:首页 > 搜索 > 正文
SSOJ1093USACO健康的荷斯坦奶牛
2620+

题目大意:有m种饲料,n种维生素,如何选最少种类的饲料,使得选择的饲料含有n种维生素且各种维生素不低于限制?

题目描述

纪念“逝去”的余世剑(cao shuo啊)

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

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

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

输入

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

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

第3行:一个整数G(1<=G<=15),表示可用来喂牛的饲料的种数。

下面G行,第n行表示编号为n饲料包含的各种维他命的量的多少。

输出

输出文件只有一行,包括

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

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

如果有多个解,输出饲料序号最小的(即字典序最小)。

样例输入

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

样例输出

2 1 3

解题思路

暴力枚举每一种饲料选不选,即填0和1,填完后验证是否满足条件——统计各种维生素的量,若都达到基本需求,则可行,记录最小值及方案。

程序实现

暴力搜索,时间复杂度O(2^n * m*n)。

加了个最优性剪枝,如果当前选择的饲料种数超过最优值,后面不需要再看下去了。

二进制暴力枚举,对应位置的1表示选择对应位置的饲料,接着还是统计维他命、记录最优值、最优方案。

二进制+广搜,一开始一种饲料都不选,然后选1种饲料,再接着选2种饲料……直到选择c种饲料满足需求为止。需要保证从小到大枚举,字典序才满足要求,即|1的时候应从小到大;还有就是去重,两个1的可以有两种途径|出来,两个位置的单个1分别或另外一个1,三个1的方案就更多了,避免队列中出现重复状态,定义f数组记录数字是否入队过,入队过的话不再入队。

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ1093USACO健康的荷斯坦奶牛:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!