在某些约束条件下找到项目最佳组合的算法

在某些约束条件下找到项目最佳组合的算法

这个问题是最大加权间隔调度算法的一种变化。DP算法对于朴素问题具有多项式复杂度，

O(N*log(N))

其

O(N)

空间具有复杂性，而对于该变异问题，其

O(2^G* N * logn(N))

具有

O(2^G * N)

空间复杂度，其中

G

，分别

N

代表组/子集（此处为5）和区间的总数。

如果x_i不代表间隔，则问题出在NP，其他解决方案也已证明。

首先让我解释最大加权间隔调度的动态规划解决方案，然后解决变异问题。

• 给定间隔的起点和终点。让

  start(i)

  ，

  end(i)

  ，

  weight(i)

  来开始，结束点，在时间间隔的间隔长度

  i

  分别。
• 根据起点的升序对时间间隔进行排序。
• 让间隔的排序顺序为

  1, 2, ... N

  。
• 让我们

  next(i)

  代表不与interval重叠的下一个间隔

  i

  。
• 让我们

  S(i)

  仅考虑作业将子问题定义为最大加权间隔

  i, i+1, ... N

  。

• S(1)

  是解决方案，它考虑来自所有作业

  1,2,... N

  并返回最大加权间隔。
• 现在让我们

  S(i)

  递归定义。

。

S(i)  = weight(i)       if(i==N) // last job      = max(weight(i)+S(next(i)), S(i+1)

此解决方案的复杂度为

O(N*log(N) +N)

。

N*log(N)

寻找

next(i)

所有工作，并

N

解决子问题。空间

O(N)

用于节省子问题解决方案。

现在，让我们解决这个问题的变体。

• 让我们共同查看X中的所有间隔。每个间隔都属于集合S_1，… S_5中的一个。
• 让

  start(i)

  ，

  end(i)

  ，

  weight(i)

  ，

  subset(i)

  来开始，结束点，间隔长度，间隔的子集

  i

  分别。
• 根据起点的升序对时间间隔进行排序。
• 让间隔的排序顺序为

  1, 2, ... N

  。
• 让我们

  next(i)

  代表不与interval重叠的下一个间隔

  i

  。
• 让我们将一个子问题定义为

  S(i, pending)

  仅考虑作业的最大加权间隔

  i, i+1, ... N

  ，它

  pending

  是子集的列表，我们必须从中选择一个子集。

• S(1, {S_1,...S_5})

  是解决方案，它考虑所有作业

  1,...N

  ，为每个作业选择一个间隔

  S_1,...S_5

  并返回最大加权间隔。
• 现在让我们

  S(i)

  递归定义如下。

。

S(i, pending)  = 0    if(pending==empty_set) // possible combination    = -inf if(i==N && pending!={group(i)}) // incorrect combination    = S(i+1, pending) if(group(i) not element of pending)    = max(weight(i)+S(next(i), pending-group(i)),          S(i+1, pending)

请注意，我可能错过了一些基本情况。

该算法中的复杂性

O(2^G * N * logn(N))

与

O(2^G * N)

空间。

2^G * N

表示子问题的大小。

据估计，对于的小值

G<=10

和的高值

N>=100000

，此算法运行很快。对于的中等值

G>=20

，

N<=10000

该算法也应较低。对于的高值

G>=40

，算法不会收敛。