子集和布套 [英] Subset and Set Cover

问题描述

我们给了很多锁，要打开这些锁，我们需要确切的那个人才能打开该锁.给定我们拥有的人数和需要打开的锁的数量，我们需要一个规范，说明如何在可用人员之间分配密钥，以便任何数量的需要打开该锁的人员都可以打开它，但不能少所需数量的人可以打开它.

We are given a number of locks and to open these locks we need exactly that set of people to open that lock. Given the number of people we have and the number of locks that needs to opened, we need a specification on how to distribute the keys amongst the available people such that any number of required people to open that lock can open it, but no group less that number of required people can open it.

人数将在1-9范围内，而打开锁所需的人数将在0-9范围内

The number of people will be in range of 1-9 and number of people required to open the lock will be in range of 0-9

请考虑以下示例

可用人数= 2

所需数量= 1 回答:{{0}，{0}}

Number of required = 1 Ans :{{0},{0}}

其中任何一个都可以打开它，因此它们都具有相同的键.

Any one of them can open it, so they are both given the same keys.

可用人数= 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}}

Ans: {{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}}

有人可以帮我解决这个问题吗?

Can someone please help me with how to go about this question.

谢谢

推荐答案

让 n 为总人数，让 m 为所需的最低人数打开所有的锁.

Let n be the total number of people, and let m be the desired minimum number of people to open all the locks.

然后，有两个要求:

• 对于每个锁，任何一组 m 个人都必须包含至少一个具有该锁密钥的人.换句话说，没有给定密钥的一组人必须比 m 人包含更少的.因此，每个密钥必须至少分配给 n  -  m   +  1个人.
• 对于每组 m −  1个人，必须至少有一个他们没有钥匙可锁的锁.换句话说，如果您转而查看具有 n  - - m   +  1个人的其他所有人"集，您可以说，对于每组 n   −  m   +  1个人，必须至少有一个仅键由该集合持有.

• For each lock, any set of m people must contain at least one person with the key to that lock. In other words, the set of people without a given key must contain fewer than m people. So each key must be distributed to at least n − m + 1 people.
• For each set of m − 1 people, there must be at least one lock that none of them has the key to. In other words, if you turn this around at look at the "everyone else" set, which has n − m + 1 people, you can say that for every set of n − m + 1 people, there must be at least one key that is only held by that set.

将这两个要求放在一起，实际上，我们在(键)和( n  - m   +  1个人).

Putting these two requirements together, we actually have a one-to-one mapping between (keys) and (sets of n − m + 1 people).

因此，您只需要查找所有 n  -  m   +  1个人(在O(2 ⁿ )时间，并且在O( C ( n ，  n  -  m   +  1))时间.为每个集合创建一个密钥，并将其分发给该集合中的人.

So you just need to find all sets of n − m + 1 people (which is trivial to do in O(2ⁿ) time, and not too hard to do in O(C(n, n − m + 1)) time). For each set, create a key and distribute it to the people in that set.

这篇关于子集和布套的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！