我需要找到一种有效的算法来找到一组最佳二进制向量，使得每个索引都有一个位，该位设置在集合中的至少一个向量中。
有趣的动机：我想闯入一座城堡并偷走它的宝藏。为了做到这一点，我必须解锁 4 扇门：蓝色门、红色门、黄色门和绿色门。有 3 个小矮人，每个人都有一套不同的钥匙。矮人 1 有：蓝键和红键。矮人 2 有：红键和黄键。矮人 3 有：蓝键和绿键。我想杀掉最少数量的小矮人才能进入城堡。所以在这种情况下，很明显我们应该只杀死 dwarf 2 和 dwarf 3 来获得所有的密钥，而没有必要杀死 dwarf 1。
一般来说，我们有 n 个大小为 m 的二进制向量（n 个小矮人和 m 个门）：a0,a1....a(n-1)。我们需要一组向量，以便向量中的每个索引至少有一个键。如果a1[5]=1，那么我们知道第2个向量的第6位被设置。意思是 dwarf #2 有键 #6。开头的例子其实是这样的： a0 (1,1,0,0) a1 (0,1,1,0) a2 (1,0,0,1) 所以我们选择向量：a1,a2 得到最小向量的全覆盖。
蛮力朴素算法是尝试每个选项，然后返回具有最少向量的解决方案，但由于有 n 个向量，因此有 2^n 个选项。
接下来我想到了一个贪心算法，它每次都采用具有最多键的向量。但这里有一个反例证明这种方法是错误的：
- a0 (1,1,1,0,0,0) --贪婪和错误的选择--
- a1 (1,0,0,1,0,0)
- a2 (0,1,0,0,1,0)
- a3 (0,0,1,0,0,1)
使用此算法，我们将选择所有 4 个向量，但最优解只有 3 个向量 {a1,a2,a3}。
现在，我想到了另一种贪心算法，我们选择具有最稀有键的向量（如果出现平局，我们搜索下一个稀有键，依此类推），但后来我又找到了一个反例：
- a0 (1,1,1,0,0,0) --贪婪和错误的选择--
- a1 (1,0,0,1,0,0)
- a2 (0,1,0,0,1,0)
- a3 (0,0,1,0,0,1)
- a4 (0,0,0,1,0,0)
- a5 (0,0,0,0,1,0)
- a6 (0,0,0,0,0,1)
在这个例子中，所有索引都具有相同的“稀有度”（2），所以我们最终选择了 a0，尽管具有 a0 的 sulotion（例如 {a0,a1,a2,a3}）至少有 4 个向量并且最优解有只有 3 个 {a1,a2,a3}。
我认为也许如果我会消除作为另一个向量子集的向量（例如 a6 是 a3 的子集），那么这个算法可能会起作用，但即便如此，检查这将花费 n！。
我希望你能帮助我找到一个有效的算法或帮助我证明这种算法不存在。