算法挑战合并集合
给定n组数字。每个集合包含一些从1到100的数字。如何选择要合并到特殊规则下最长集合的集合，只有两个非重叠集合可以合并。 [1,2,3]可以与[4,5]合并，但不合并[3,4]。什么将是一个有效的算法合并成最长的集合。算法挑战合并集合
我的第一次尝试是形成一个n乘n的矩阵。每行/列代表一个集合。如果两个集合重叠，则条目（i，j）等于1，则条目（i，i）存储集合i的长度。那么问题就变成了我们可以同时执行行和列操作，以在左上角创建对角线子矩阵，其轨迹尽可能大。
但是，我陷入了如何高效地执行行和列操作以在左上角形成这样的对角子矩阵。
正如在评论（最大覆盖问题）中已经指出的那样，您有一个NP-hart问题。幸运的是，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第012个元素位于第j个集合中，A(i,j)=0意味着第i个元素不在第j个集合中。
现在，x代表我们选择集：如果x_j=1超过设定j选择，如果x_j=0 - 比没有选择！
由于每一个元素必须是最多的一组，我们选择b=(1, 1, 1, ..., 1)：如果我们把它含有i个元素两套，比(Ax)的i个元素是至少2
剩下的唯一问题是什么f？我们尝试最大化联合中的元素数量，因此我们选择f_j=-|set_j|（减去由于最小<→最大转换），其中|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作为位域。
灿您请首先发布您自己的尝试是要解决什么问题？那么我们可以帮助您解决具体的问题。 – EkcenierK
你见过最大覆盖率问题吗？你的问题听起来类似于https://en.wikipedia.org/wiki/Maximum_coverage_problem –