algorithm - 包含排除的动态规划技术

Question

有N个士兵(编号从1到N)。每个士兵都有 M 种不同技能(从 1 到 M 编号)中的一些技能子集。一支军队的技能组合是其组成士兵的技能组合。有多少不同的士兵子集满足有特定技能要求 Problem

根据解释，问题简化为找到这些数字的子集的数量，其 OR 正好等于所需的值，比如 req

令 f(i) 为满足 j OR i = i 的数字 j 的个数，则答案为
∑i(−1)^popcount(i xor req)(2^f(i) −1) 对于所有 i 使得 i OR req 是 req

这个公式是怎么来的，popcount是怎么描述它加减的。

Answer 1

这是我的看法。解决方法:不是对拥有某些技能的群体进行推理，让我们对没有某些技能的士兵群体进行推理。
因为这第二个属性可以很好地从组传播到所有成员。

在我们开始之前，稍微简化一下:

不失一般性，我们可以过滤掉至少有一项技能在要求的集合之外的士兵。因为子集的技能必须恰好是所需的技能集，所以永远不需要那些知道太多的聪明士兵。

从现在开始，我们假设所需的技能集是 {1, ... , R}而且士兵的技能介于1之间和 R .

我们将需要 A_i 的定义(其中 i 属于 {1,..,R} ):

A_i : 一组有技能的士兵 i 在他们的团队技能组合中。

换句话说，A_i 中的一组( inter 表示交集)是一组至少有一名士兵拥有技能编号 i 的组.

现在如果i<j ,

A_i inter A_j = 有技能的士兵组 i和 j 在他们的团队技能组合中。

换句话说，A_i inter A_j 中的一组是一个至少有一个属性的群

• 一名拥有两种技能的士兵编号i和 j .
• 两个士兵，一个有技能i ，一身本事j .

和

A_1 inter A_2 ... inter A_R

是一组有技能的士兵1,.., R在他们的团队技能中。

问题提出的问题可以用A_i表示:

A_1 inter A_2 ... inter A_R 的大小是多少？ ？

等于

2^2^R - size( comp(A_1) union comp(A_2) ... union comp(A_R) )

哪里comp(A)是互补集。

现在，我们可以应用包含排除原则。

还有一个技巧可以让它变得可计算:

如果I是 {1,..,R} 的子集, 然后是

intersection(comp(A_j) for all j in I)

是I中没有技能的士兵组(作为一个组) .请注意，这样一个组中的士兵正是没有任何技能的士兵 I .让我们定义 g(I)作为集合中没有任何技能的士兵数量 I .这样，我们就有了

size( intersection(comp(A_j) for all j in I) ) = 2^g(I)

最后，我得到的结果是:

2^2^R - sum( (-1)^(size(I)+1) * 2^g(I) , for each I subset of {1,..,R} and I non-empty)

希望对您有所帮助。如果还有什么不清楚的地方，请告诉我。