定义
- 设置
P={e1,e2,...,en}，P有n个不同的元素，在其中枚举为ei's - 集合
I={e1',e2',...,en'}、I具有至少一个与P的某个元素相似的元素。CCD_ 8中的元素数量不必等于CCD_ - 每个
I都有一个与其相关联的权重Q，它描述了使用它的成本。Q>0
你必须帮助我设计一个算法，它以集合P为输入，并且一些(比如其中的k个)I集合，用I1、I2…表示，Ik，确切地说是k，Q值，由Q1，Q2，…表示，问题。Q1表示使用集合I1的成本，依此类推。
你必须选择一些I，比如I1，I2，使得当它们都统一在一起时，它们产生集合P'，并且P是其子集
请注意，一旦您找到一个I的选择，它就会有一个与之相关的成本。
您还必须确保该成本尽可能地为最小。
输入
- 输入一个Set
P - 输入集合
I的列表，IList={I1，I2，…In} - 输入集合
Q的列表，QList＝{Q1，Q2，…Qn} - CCD_ 19CCD_
输出
P'=Ia并集Ib。。。并集InP' ⊂ P- 使Qa+Qb+Qn是最小值
还要提到算法的时间和空间复杂性
样本输入
P={a,b,c}
I1={a,x,y,z} Q1=0.7
I2={b,c,x} Q2=1
I3={b,x,y,z} Q3=2
I4={c,y} Q4=3
I5={a,b,c,y} Q5=9
样本输出
P1 = I1 U I2 COST=Q1+Q2=1.7
P2 = I1 U I3 U I4 COST=Q1+Q3+Q4=5.7
P3 = I5 COST=Q5=9
And:P⊂P1,P⊂P2,P⊂P3
The P COST : 1.7<5.7<9
And then what we want is:
P1 = I1 U I2 COST=Q1+Q2=1.7
这里有一些简化问题的建议。
我们首先复制所有的I集合，并将它们称为I1'、I2'、.、.、.
现在，我们应该做的第一项工作是从重复的I'集合中删除不需要的元素。这里不需要的是指对主集合CCD_ 30没有贡献的元素。
我们丢弃所有那些甚至不具有CCD_ 32的单个元素的CCD_。
现在假设P中有一些n元素，我们现在可以肯定地知道，I'集合只不过是主集合的子集，并且每个子集都有与其相关的代价Qi。
我们只需要选择一些子集，使它们一起覆盖主集合。以最低成本为准。
我们将使用基于位的表示法来表示主集合和子集。
如果集合P中有n元素，则表示中将有n个比特。因此，主集合将由<1,1，。。。1> (n1’s)。它的子集将由位集表示，主集的位集中缺少一些1。因为I's也是子集，所以它们也将具有表示它们所表示的子集的一些二进制表示。
为了有效地解决这个问题，让我们假设有这么多内存可用，如果将位集视为二进制数字，我们可以在恒定时间内将位集索引到某个内存位置。
这意味着，如果我们有，假设n = 4，所有的子集都可以表示通过从0到15的不同值(参见它们从0000(空集)到1111(主集)的二进制表示，当主数组的位置i处的元素存在于子集中时，我们在比特集中的该位置放置1)。当CCD_ 42较大时也是如此。
现在，具有用于该集合的基于比特集的表示法，由比特集b1和b2表示的两个集合的并集将由b1|b2表示。其中CCD_ 46是逐位OR运算。
当然，我们不需要那么多的内存位置，因为并不是父集的所有子集都可以作为I's使用。
算法
：
这里使用的算法思想是基于位集的动态编程。
假设我们有一个大数组，即COST，其中COST[j]表示拥有子集的成本，由j的位集表示法表示。
首先，我们将选择给定子集的成本(根据I's)放在COST数组中它们各自的索引中，并在所有其他位置放一个非常大的值，比如INF。
我们要做的是，适当地填充数组，然后一旦它被适当地填充，我们将通过查看值COST[k]来获得最小成本的答案，其中k以二进制表示设置了所有比特。
现在我们将重点讨论如何正确填充数组。
这是一项相当简单的任务，我们将迭代COST数组，K次数，其中K是我们拥有的I'集的数量。
对于每个I's集合，我们将其称为二进制表示BI'。我们对BI'和当前索引(idx)的比特表示进行OR运算，得到的是新集合，它是当前索引和BI'表示的集合的UNION，我们将这个新集合称为S'，它的最终二进制表示为BS'。
我们将查看COST[BS']，如果我们看到这个COST大于COST[BI'] + COST[idx]，我们将更新COST[BS']处的值。
以类似的方式继续，在运行结束时，我们在COST[BP]处获得最小成本，其中BP是P的位集。
为了跟踪参与I's，他们实际上对P的形成做出了贡献，我们可以在更新任何索引时注意。
时间复杂性
：O(2^n*K)，其中K是I集合的数量，n是P中元素的数量。
空间复杂性：O(2^n)
注：由于假设比特表示是可直接索引的，因此对于I0和k的大值，该解决方案可能不太可行。