我将尝试用数学语言解释问题。 假设我有一组物品X = {x_1, x_2, ..., x_n}。的每个项目都X属于其中一组S_1, S_2, ..., S_5。我认为所有的子集X，包括5个项目： {x_i1, x_i2, ..., xi5}所以x_i1属于S_1，…，x_i5belogns来S_5。 一些子集被认为是正确的，而一些子集被认为是不正确的。如果子集不包含冲突项，则认为该子集正确。我有一个函数f1来确定一对项目是否冲突。 我还有一个函数f2，可以比较这些正确的子集并说出哪个子集更好（它们也可能相等）。 我需要找到最佳的无冲突子集。
X = {x_1, x_2, ..., x_n}
X
S_1, S_2, ..., S_5
{x_i1, x_i2, ..., xi5}
x_i1
S_1
x_i5
S_5
我曾经使用过的算法： 我构建了所有子集，丢弃了不正确的子集。然后，我使用f2作为排序函数对正确的子集进行了排序，并获得了最佳的子集（我使用了快速排序算法）。就大量子集而言，此过程花费的时间不足。
在时间消耗方面是否有更好的方法？
更新 让我们将x_i视为具有整数端点的间隔。如果2个间隔不相交，则f1返回true，否则返回false。f2比较子集中的间隔总和长度。
这个问题是最大加权间隔调度算法的一种变化。DP算法对于朴素问题具有多项式复杂度，O(N*log(N))其O(N)空间具有复杂性，而对于该变异问题，其O(2^G * N * logn(N))具有O(2^G * N)空间复杂度，其中G，分别N代表组/子集（此处为5）和区间的总数。
O(N*log(N))
O(N)
O(2^G * N * logn(N))
O(2^G * N)
G
N
如果x_i不代表间隔，则问题出在NP，其他解决方案也已证明。
首先让我解释最大加权间隔调度的动态规划解决方案，然后解决变异问题。
start(i)
end(i)
weight(i)
i
1, 2, ... N
next(i)
S(i)
i, i+1, ... N
S(1)
1,2,... N
。
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)用于节省子问题解决方案。
O(N*log(N) + N)
N*log(N)
现在，让我们解决这个问题的变体。
subset(i)
S(i, pending)
pending
S(1, {S_1,...S_5})
1,...N
S_1,...S_5
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表示子问题的大小。
2^G * N
据估计，对于的小值G<=10和的高值N>=100000，此算法运行很快。对于的中等值G>=20，N<=10000该算法也应较低。对于的高值G>=40，算法不会收敛。
G<=10
N>=100000
G>=20
N<=10000
G>=40
