算法挑战合并集合
给定n组数字。 每个集合包含一些从1到100的数字。如何选择要合并到特殊规则下最长集合的集合，只有两个非重叠集合可以合并。 [1,2,3]可以与[4,5]合并，但不合并[3,4]。 什么将是一个有效的算法合并成最长的集合。
我的第一个尝试是形成一个n乘n的矩阵。 每行/列代表一个集合。 如果两个集合重叠，则条目（i，j）等于1，则条目（i，i）存储集合i的长度。 那么问题就变成了我们可以同时执行行和列操作，以在左上角创建对角线子矩阵，其轨迹尽可能大。
但是，我陷入了如何高效地执行行和列操作以在左上角形成这样的对角子矩阵。
正如评论中已经指出的那样（最大覆盖问题）你有一个NP哈特问题。 幸运的是，matlab为整数线性编程提供了求解器。
所以我们试图将问题简化为以下形式：
min f*x subject to Ax<=b , 0<=x
有n个集合，我们可以将一个集合编码为0和1的向量。 例如(1,1,1,0,0,...)将表示{1,2,3}和(0,0,1,1,0,0...) - {3,4} 。
A每一列代表一组。 A(i,j)=1意味着第i个元素在第j个集合中， A(i,j)=0意味着第i个元素不在第j个集合中。
现在， x表示我们选择的集合：如果x_j=1比选择了集合j ，如果x_j=0 - 比未选中！
由于每个元素都必须至多在一组，我们选择b=(1, 1, 1, ..., 1)如果我们把包含两套i个元素，比i的个元素(Ax)至少2。
剩下的唯一问题是f是什么？ 我们试图最大化联合中的元素数量，所以我们选择f_j=-|set_j| （由于min→max转换而减去）， |set_j| - 第j组元素的数量。
把它全部在MATLAB中，我们得到：
f=-sum(A)
xopt=intlinprog(f.',1:n,A,ones(m,1),[],[],zeros(n,1),ones(n,1))
f.' - 成本函数列 1:n - x中的所有n元素都是整数 A - 编码n组 ones(m,1) - b=(1,1,1...) ，有m=100元素 [],[] - 没有形式Aeq*x=beq约束 zeros(n,1), 0<=x必须成立 ones(n,1), x<=1跟随其他约束，但也许它会帮助解算器一点点 您可以将组表示为位域。 按位和操作产生零将指示不重叠的集合。 根据底层数据类型的宽度，您可能需要执行多个操作。 例如，对于64位机器字大小，我需要两个字来覆盖1到100作为位域。
链接地址: http://www.djcxy.com/p/40223.html