我有一些带有权重的活动，我想通过最大化总权重来选择非重叠活动。这是已知的问题，并且存在解决方案。
在我的情况下，我可以在持续时间不变的情况下，在一定程度上延长活动的开始时间。这将给我一些灵活性，并且我可能会提高利用率。
示例场景类似于以下内容，其中所有活动都应在时间间隔（0-200）之间：
(start, end, profit)
a1: 10 12 120
a2: 10 13 100
a3: 14 18 150
a4: 14 20 100
a5: 120 125 100
a6: 120 140 150
a7: 126 130 100
没有灵活性，我会选择（（a1，a3，a6）]就是这样。另一方面，对于给出了[[t的任何任务，我都有shift shifting向左/向右移动最多 t个单位。在这种情况下，我可能会提出此计划，并且可以选择除a7以外的所有任务，因为无法通过轮班避免冲突。
t: 5
a1: 8 10 120 (shifted -2 to left)
a2: 10 13 100
a3: 14 18 150
a4: 18 23 100 (shifted +4 to right)
a5: 115 120 100 (shifted -5 to left)
a6: 120 140 150
在我的问题中，就活动持续时间而言，我的总时间很大。虽然平均活动时间为10秒，但我的总时间甚至为10000秒。但是，这并不意味着可以选择所有活动，因为对于某些活动来说，将灵活性转移到不重叠是不够的。可以说是cluster1和a5 ，a6和a7是cluster2。通过将某些集群左右移动，可以及时扩展每个集群。这样，我可以选择比原始活动选择问题更多的活动。但是，我不知道如何决定要转移到左或右的任务。 我的期望是找到总利润将以某种方式局部最优的接近最优的解决方案。我不需要全局最优值。我也没有关于集群利用率的任何标准。即，我不能保证每个集群的最小活动数量等。实际上，这些集群是我用视觉描述的。没有定义的集群。但是，在时域中，活动以某种方式被分为簇。也是在我的问题中，有许多活动重叠，并且有很大的空白空间，没有活动，并且又出现了另一类重叠活动，即
a1，a2，a3和a4
而且活动的开始和结束时间都是整数，因为我可以忽略小数。我将进行大约50项活动，这些活动的平均持续时间为10次。时间窗口大约是10000。
对此问题有可行的解决方法吗？
取决于剩余群集的最大大小，有几种方法。如果小于20（或者甚至小于30，取决于您希望程序在几秒钟还是几分钟内运行），则可以使用贪婪的方法将对给定集群中所有活动子集的搜索结合起来。换句话说：如果您正在处理N个元素的子集，请尝试其2^N个可能的子集中的每个子集（好吧，如果我们忘记了空的子集，请尝试2^N-1），检查是否可以在该特定子集中安排活动。非重叠方式，并选择符合条件且具有最大和的子集。
我们如何检查给定的活动子集可以不重叠的方式进行安排？让我们按照它们的升序对其进行排序，并从左到右对其进行处理。对于每项活动，我们都会尽早安排它，以确保它与我们已经考虑过的活动不交叉。因此，群集中的第一个活动总是在开始时间t早于最初计划的时间开始，第二个活动在第一个活动结束时开始，或者在t早于最初计划的时间开始（以较大者为准），依此类推。如果在任何时候我们都无法以与上一个活动不重叠的方式安排下一个活动，那么就没有办法以非重叠的方式安排该子集中的活动。该算法采用O(NlogN) time，总体上，每个群集都在O(2^N * NlogN)中进行处理。再次注意，此功能增长非常快，因此，如果要处理足够大的群集，则此方法不适用。
===
另一种方法特定于您提供的其他限制。如果活动的开始和结束且参数t都以整数秒为单位来度量，并且t大约为2分钟，则每个群集的问题都设置在一个小的离散空间中。即使您可以将任务定位为从非整数第二个值开始，但总会有一个仅使用整数的最佳解决方案。 （为证明这一点，请考虑一个不使用整数的最佳解决方案-由于t是整数，因此您始终可以从最左边开始向左移动任务一点，以便它从整数值开始。）
知道开始时间和结束时间是离散的，您可以构建一个DP解决方案：按照活动结束的升序*处理活动，并记住您可以从前1、2，...获得的最大权重之和。 ..，如果给定活动在时间x结束，则从activity_start - t到activity_start + t的每个x N个活动。如果我们将该记忆函数表示为f[activity][end_time]，则递归关系为f[a][e] = weight[a] + max(f[i][j] over all i < a, j <= e - (end[a] - start[a])，这大致翻译为“如果活动a在时间e结束，则先前的活动必须在a开始或之前结束]-因此，让我们选择上一个活动及其终点的最大总重量，然后加上当前活动的重量”。
*同样，我们可以证明至少有一个最优答案可以保留此排序，即使可能还有其他不具有此属性的最优答案
我们可以更进一步，消除先前活动的迭代，而是将这些信息编码为f。然后，其定义将更改为“ f[a][e]是第一个a活动的最大可能总权重，如果没有一个活动在e之后结束”，则递归关系将变为f[a][e] = max(f[a-1][e], weight[a] + max(f[a-1][i] over i <= e - (end[a] - start[a])]))，其计算复杂度将为[ C0]，其中O(X * N)是放置任务开始/结束的离散空间的总跨度。
我假设您不仅需要计算最大可能的重量，还需要计算选择以获得最大重量的活动，甚至可能需要精确地计算每个活动的开始时间。值得庆幸的是，我们可以从X的值中得出所有这些值，或者在计算f的同时进行计算。后者更容易推论，因此让我们介绍第二个函数f。 g[activity][end]返回一个对g[activity][end]，从本质上为我们指出了(last_activity, last_activity_end)中最佳权重所使用的确切活动及其时机。
让我们看一下您提供的示例以说明其工作原理：
f[activity][end]
我们按活动的结束时间对其进行排序，从而交换a7和a6。
(start, end, profit)
a1: 10 12 120
a2: 10 13 100
a3: 14 18 150
a4: 14 20 100
a5: 120 125 100
a6: 120 140 150
a7: 126 130 100
和f的值：g，这意味着第一个活动可能会在7到17之间结束，并且花费120。所有其他f[1][7] = 120, f[1][8] = 120, ..., f[1][17] = 120的f[1][i]应该设置为0。i，表示g[1][7] = (1, 7), g[1][8] = (1, 8), ..., g[1][17] = (1, 17)值中包含的最后一个活动是f[1][i]，并且结束于a1。 i以外的所有g[1][i]的i是未定义/不相关。
[7, 17]不能在时间i结束的a2，让我们分配i，这实际上意味着我们不会在这些答案中使用活动f[2][i] = f[1][i], g[2][i] = g[1][i]。对于所有其他a2，即在i间隔中，我们具有：[8..18]f[2][8] = max(f[1][8], 100 + max(f[1][0..5])) = f[1][8]
f[2][9] = max(f[1][9], 100 + max(f[1][0..6])) = f[1][9]。这是第一次，当第二子句不只是纯100，例如f[2][10] = max(f[1][10], 100 + max(f[1][0..7]))。实际上，它是f[1][7]>0，这意味着我们可以进行活动100+f[1][7]=220，以使其在时间a2结束的方式进行移动，并获得总权重10。我们将继续以这种方式为所有220计算f[2][i]。
i <= 18的值为：g，g[2][8]=g[1][8]=(1, 8)，g[2][9]=g[1][9]=(1, 9)，因为在这种情况下，最好选择活动g[2][10]=(2, 10)并在时间a2结束。
我希望这种情况如何继续下去的模式是可见的-我们计算出结束时所有10和f的值，然后在上一个活动的所有可能结束时间g中选取最大值f[N][e] 。配备辅助功能e，我们可以向后遍历这些值以找出确切的活动和时间。即，我们使用的最后一个活动及其时间在g中。我们称它们为g[N][e]和A。我们知道A从T开始。然后，先前的活动必须在该时刻或之前结束-因此，让我们看一下它的T-(end[A]-start[A])，依此类推。]
请注意，即使您不将任何内容划分为集群，该方法也可以使用，但是通过该划分，可以减少计划任务的空间大小，并减少运行时的时间。
您可能会注意到，这些解都不是输入大小的多项式。我感觉到您的问题没有通用的多项式解，但是我无法通过将另一个NP完全问题简化为证明。阅读还原/更好的一般解决方案真的很好奇！