集合划分问题

集合划分问题（set partitioning problem）在给定的子集族中选择若干集合，使全集中每个元素恰好出现一次，并优化所选集合的总成本或收益。它既不允许遗漏，也不允许重复覆盖；这两个要求同时存在，区别于只要求至少覆盖一次或至多使用一次的模型。

例如四段必须执行的运输任务组成 $U=\{1,2,3,4\}$。每个可选班次可以完成一个子集，成本如下：A完成一、二，成本三；B完成三、四，成本三；C完成一、三，成本二；D完成二、四，成本五；E一次完成全部四段，成本七。每段任务恰好执行一次时，选A和B需六，选C和D需七，单选E也需七，因此最低为六。

恰好一次的等式模型

令 $a_{ij}=1$ 表示元素 $i$ 属于候选集合 $S_j$，否则为零；$x_j\in \{0,1\}$ 决定是否选中。最小成本形式为 $$\begin{array}{cc}min& \sum _j{c}_j{x}_j,\\ \sum _j{a}_{ij}{x}_j& =1(i\in U).\end{array}$$ 左边是元素被选中集合覆盖的次数，所以等于一恰好表达划分。主例四行是 $$\begin{array}{cc}{x}_A+x_C+x_E& =1,\\ x_A+x_D+x_E& =1,\\ x_B+x_C+x_E& =1,\\ x_B+x_D+x_E& =1.\end{array}$$ 模型中的候选集合受到业务限制；不能把“任选任意子集”与“只能从清单挑选”混淆。最大收益版本同样可用这些等式，只需改变目标方向。

色块表示该班次包含该任务。A与B两行互不重叠，并且四列都被覆盖；不是把所有低成本行一概选入。

主例的最优性可以不依靠求解器：覆盖元素一的集合只能是A、C、E。若选A，包含一、二的其他集合均不能再选，剩下三、四只能由B一起覆盖，成本六；若选C，剩下二、四必须由D覆盖，成本七；若选E，已经覆盖全部，成本七。这三个分支穷尽所有划分。

从第一个未覆盖元素递归

假定候选集合均非空。任何合法划分都恰有一组包含第一个未覆盖元素，因此可依次尝试所有包含它、且不与已覆盖部分相交的候选集合。选入后，该元素及同组元素都从剩余集合移除；空剩余集合是完成解，无候选可选则此分支不可行。

下面把剩余元素集作为记忆化状态。返回最小成本与所选集合下标；没有合法划分返回 $+\mathrm{\infty }$ 与空下标。成本允许负数，因为每个非空集合只能用一次，有限集合族不会导致无限下降。

Python 3

from functools import lru_cache
import math

def set_partition(universe, subsets, costs):
    u, sets, c = tuple(universe), tuple(map(frozenset, subsets)), tuple(costs)
    if len(set(u)) != len(u) or len(sets) != len(c):
        raise ValueError("distinct universe and matching costs required")
    allowed = frozenset(u)
    if any(not s or not s <= allowed for s in sets):
        raise ValueError("nonempty subsets of universe required")
    if any(not math.isfinite(v) for v in c):
        raise ValueError("finite costs required")
    @lru_cache(None)
    def solve(left):
        if not left:
            return 0, ()
        first = next(x for x in u if x in left)
        best = (math.inf, ())
        for j, group in enumerate(sets):
            if first in group and group <= left:
                value, rest = solve(left - group)
                if value < math.inf and c[j] + value < best[0]:
                    best = (c[j] + value, (j,) + rest)
        return best
    return solve(allowed)

print(set_partition([1,2,3,4], [{1,2},{3,4},{1,3},{2,4},{1,2,3,4}],
                    [3,3,2,5,7]))
# (6, (0, 1))

剩余集合每步严格缩小，保证停止。每个合法解在“第一个未覆盖元素所属集合”处分到唯一分支；递归子问题保持不交与覆盖条件，由剩余元素个数归纳证明最优性。若资源数为 $m$、候选数为 $n$，最多有 $2^m$ 个状态；计入集合操作与保存路径，这个教学实现的时间可界为 $O(nm{2}^m)$，空间可界为 $O(m{2}^m+nm)$，不是适合超大资源集的多项式算法。

变式。 去掉A后，C+D和E都需七，仍可划分；若只保留A、C、D而去掉B、E，C+D仍可行。若只保留A、C，元素四无任何覆盖，问题不可行。空全集与空集合族对应成本零的空划分，但非空的可选空集合需另行处理，本文代码主动拒绝，以免“覆盖状态不变”的递归循环。

班组排班常把一整条合法工作日程作为一列；可能的日程数量很大时，可用列生成按需要产生候选列。列生成先解连续松弛，并不会仅凭列生成停止就解决所有整数划分要求。