集合打包问题

集合打包问题（set packing problem）从给定子集族中选取若干集合，要求任意两个选中集合不共享元素，并使选中集合的总收益最大。集合中的元素可以表示时间片、机场停机位或不可同时分配给两项任务的资源；“打包”在这里指选择互不冲突的资源组合，而非把物品装进有容量的箱子。

设资源全集为 $U=\{1,2,3\}$，四个可选任务为 $$\begin{array}{cc}A& =\{1,2\},v_A=7,\\ B& =\{1\},v_B=4,\\ C& =\{2\},v_C=4,\\ D& =\{3\},v_D=2.\end{array}$$ 先挑收益最大的A，再挑不冲突的D，收益只有九。改选B、C、D，收益为十；单项收益较高并不等于组合收益最高。

关联矩阵与冲突图

令 $a_{ij}=1$ 表示资源 $i$ 属于任务集合 $S_j$，否则为零。对二元选择变量 $x_j$，模型为 $$\begin{array}{cc}max& \sum _{j=1}^n{v}_j{x}_j,\\ \sum _{j=1}^n{a}_{ij}{x}_j& \le 1(i\in U),\\ x_j& \in \{0,1\}.\end{array}$$ 若两项选中任务有公共元素，该行的和至少为二，违反约束；反之，每行至多为一，就没有元素被两项同时占用。因而矩阵约束与两两不交完全等价。主例三行分别为 $x_A+x_B\le 1$、$x_A+x_C\le 1$、$x_D\le 1$。

还可以把每项任务画成一个顶点，集合相交时连边。选中任务必须构成冲突图的独立集，即不选中任何一条边的两个端点。这给出集合打包与加权独立集问题的对应，但把图画出来本身并不构成求最优算法。

每条连边表示不能同时选择。B与C虽都和A冲突，彼此并不冲突；这种结构导致逐项最大收益贪心失败。

最优解的两分支证明

若选A，则不能再选B或C，最多加D，收益不超过九。若不选A，B、C、D相互不交，收益非负，所以全部选入得到十，且这支没有更好的组合。这两个分支覆盖全部可能，故十为全局最优。这类逐分支证明也是分支定界法的基本思路。

以下小实例程序先把子集转为位掩码，随后枚举任务选择。已占用元素与新集合的掩码按位与为零，恰好表示不相交；只有通过该检查才合并资源。

Python 3

from itertools import product
import math

def set_packing(universe, subsets, values):
    u, sets, v = tuple(universe), tuple(map(frozenset, subsets)), tuple(values)
    if len(set(u)) != len(u) or len(sets) != len(v):
        raise ValueError("distinct universe and matching data required")
    index = {x:i for i,x in enumerate(u)}
    if any(not s <= set(u) for s in sets):
        raise ValueError("unknown resource")
    if any(not math.isfinite(x) for x in v):
        raise ValueError("finite values required")
    masks = [sum(1 << index[x] for x in s) for s in sets]
    best, chosen = 0, ()
    for bits in product((0,1), repeat=len(sets)):
        used, total, selected = 0, 0, []
        for j, x in enumerate(bits):
            if x:
                if used & masks[j]:
                    break
                used |= masks[j]; total += v[j]; selected.append(j)
        else:
            if total > best:
                best, chosen = total, tuple(selected)
    return best, chosen

print(set_packing([1,2,3], [{1,2},{1},{2},{3}], [7,4,4,2]))
# (10, (1, 2, 3))

每个二元组合被检查一次，任何冲突组合必在首次重复占用时被排除；其余组合恰好可行，因此返回值精确。令 $M=\sum _j|S_j|$ 为候选集合元素出现总数。当前校验为每个候选重建全集集合，连同掩码转换的预处理时间为 $O(M+n|U|)$。若暂把位掩码运算视为单位成本，随后枚举时间为 $O(n{2}^n)$；保存复制后的子集、掩码及当前选择，额外空间为 $O(M+n+|U|)$；资源很多时还应计入大整数按位操作的位复杂度。

变式。 把B收益改为三，则A+D和B+C+D都为九，最优解不唯一。若所有收益非正，允许不选任务时空集合最优；若要求每个资源恰好被使用一次，约束应改成等式，那是集合划分问题。至于至少覆盖一次的集合覆盖问题，其可行方向又与这里不同，三者不能只更换名称而复用同一组不等式。