algorithm - 子集和集封面

Question

我们有许多锁，要打开这些锁，我们需要一组人来打开那把锁。鉴于我们拥有的人数和需要打开的锁的数量，我们需要一个关于如何在可用人员之间分配 key 的规范，以便打开该锁所需的任何数量的人都可以打开它，但不能少所需人数可以打开它。

人数范围为1-9，开锁所需人数范围为0-9

考虑以下示例

可用人数 = 2

所需数量 = 1 答:{{0},{0}}

他们中的任何一个都可以打开它，因此他们都获得了相同的 key 。

可用人数 = 5

所需数量 = 3

答案:{{0, 1, 2, 3, 4, 5},{0, 1, 2, 6, 7, 8},{0, 3, 4, 6, 7, 9},{1 , 3, 5, 6, 8, 9},{2, 4, 5, 7, 8, 9}}

谁能帮我解决这个问题。

谢谢

Answer 1

令n 为总人数，令m 为打开所有锁所需的最少人数。

那么，有两个要求:

• 对于每把锁，任何一组 m 人都必须至少包含一个拥有该锁 key 的人。换句话说，没有给定键的人的集合必须少于 m 人。所以每个 key 必须分发给至少 n - m + 1 个人。
• 对于每组 m - 1 个人，必须至少有一把锁，但他们都没有 key 。换句话说，如果你反过来看看“其他人”的集合，它有 n - m + 1 个人，你可以说对于每一组n - m + 1 个人，必须至少有一个 key 仅由该集合持有。

将这两个要求放在一起，我们实际上在 (keys) 和 (n - m + 1 人的集合) 之间有一个一对一的映射。

所以你只需要找到所有 n - m + 1 个人的集合(这在 O(2ⁿ) 时间，并且在 O(C(n, n − m + 1)) 次)。为每个集合创建一个 key 并将其分发给该集合中的人。