多拟阵

多拟阵（polymatroid）是由集合容量约束确定的非负多面体。与拟阵中一个元素只能选或不选不同，多拟阵为每个元素分配一个非负实数，并要求任意子集的分配总量不超过其容量。容量满足边际递减，使按单价顺序逐步分配能够求解线性目标。

设两类任务的分配量为 $x_1,x_2$，单类上限分别为三、四，共享资源使总量不超过五。可行域为 $x_1,x_2\ge 0$、$x_1\le 3$、$x_2\le 4$、$x_1+x_2\le 5$。若每单位收益分别为五和二，先给第一类三单位，再给第二类剩余两单位，收益为十九；若反过来先给第二类四单位，收益只有十三。

总量边界切掉矩形右上角；收益较高的第一类先分配至三，最优点为 (3,2)。

集合容量的条件

有限底集为 $E$。设 $f:2^E\to ℝ$ 满足归一化 $f(\varnothing )=0$、单调性 $A\subseteq B\Rightarrow f(A)\le f(B)$，以及次模性 $$f(A)+f(B)\ge f(A\cup B)+f(A\cap B).$$ 记 $x(A)=\sum _{e\in A}{x}_e$，定义 $$P(f)=\{x\in {ℝ}_{\ge 0}^E:x(A)\le f(A)\text{ 对所有 }A\subseteq E\}.$$ 这称为 $f$ 的多拟阵；有些文献把函数对 $(E,f)$ 本身也称多拟阵。上述单调、归一化条件保证 $f\ge 0$，故零向量可行；单元素约束给出有限坐标上界，因而 $P(f)$ 是有界多面体。

例中 $f(\{1\})=3,f(\{2\})=4,f(E)=5$；唯一非平凡的次模条件是 $3+4\ge 5+0$。等式 $x(E)=f(E)$ 选出称为基多面体的面，本例是从 $(3,2)$ 到 $(1,4)$ 的线段。若 $f$ 恰为拟阵秩，则 $P(f)$ 等于独立集指示向量的凸包；一般容量如 $f(\{1\})=3$ 则已超过单元素秩所允许的一。

前缀分配的可行性与最优性

给定非负权重，排列底集使 $w_1\ge \cdots \ge w_n\ge 0$，并令 $A_i=\{1,\dots ,i\}$、$A_0=\varnothing$。定义 $$x_i^{\ast }=f(A_i)-f(A_{i-1}).$$ 单调性保证每项非负，且每个前缀恰好达到容量 $x^{\ast }(A_i)=f(A_i)$。

为证明所有子集约束都满足，任取 $B=\{i_1<\cdots <i_k\}$。加入 $i_j$ 时，$\{i_1,\dots ,i_{j-1}\}\subseteq A_{i_j-1}$。次模的边际递减性质给出 $$x_{i_j}^{\ast }\le f(\{i_1,\dots ,i_j\})-f(\{i_1,\dots ,i_{j-1}\}).$$ 逐项相加，右边望远镜抵消为 $f(B)-f(\varnothing )=f(B)$，于是 $x^{\ast }(B)\le f(B)$，可行性成立。

再置 $w_{n+1}=0$。任意可行 $x$ 的收益可按前缀重写为 $$\sum _{i=1}^n{w}_i{x}_i=\sum _{i=1}^n(w_i-w_{i+1})x(A_i)\le \sum _{i=1}^n(w_i-w_{i+1})f(A_i).$$ 所有系数非负才允许逐项使用上界。$x^{\ast }$ 在每个前缀上取等号，故达到此收益上界。这同时证明了贪心选择的全局最优性。

可运行实现与变式

下列函数接受无重复、可哈希元素、对应的非负权重字典，以及正确的容量查询 f。它返回各元素分配量，不改写输入；不枚举验证次模性，调用者须保证前提。

Python 3

def polymatroid_greedy(elements, weights, f):
    items = tuple(elements)
    if len(set(items)) != len(items):
        raise ValueError("elements must be distinct")
    if any(weights[e] < 0 for e in items):
        raise ValueError("weights must be nonnegative")
    if f(frozenset()) != 0:
        raise ValueError("f must be normalized")
    order = sorted(items, key=lambda e: weights[e], reverse=True)
    prefix = set()
    old_value = 0
    result = {}
    for e in order:
        prefix.add(e)
        new_value = f(frozenset(prefix))
        result[e] = new_value - old_value
        old_value = new_value
    return result

capacity = {frozenset(): 0, frozenset({1}): 3,
            frozenset({2}): 4, frozenset({1, 2}): 5}
answer = polymatroid_greedy([1, 2], {1: 5, 2: 2}, capacity.__getitem__)
assert answer == {1: 3, 2: 2}
assert polymatroid_greedy([], {}, capacity.__getitem__) == {}
print(answer)

循环不变量为已处理前缀的分配和等于当前 old_value=f(prefix)，未处理元素还未分配；上面的证明保证最终任意子集可行。排序耗时 $O(n\log n)$，容量查询 $n+1$ 次；由于代码每次构建不可变前缀，还需 $O(n^2)$ 元素复制时间。若一次查询时间为 $T(n)$，总时间为 $O(n\log n+n^2+nT(n))$，工作空间为 $O(n)$，不计查询器自身存储。

变式。 权重改为 $w_1=1,w_2=4$。先分配第二类四单位，再分第一类一单位，得 $(1,4)$、收益十七。证明中的上界为 $(4-1)f(\{2\})+1f(E)=12+5=17$，与结果相同。

若允许负权重，不能一律填满全体前缀：只有一个容量为一的元素、权重为负一时，填一单位收益负一，而零分配收益零。处理一般权重可仅对正权重元素运行前缀分配，其余置零。若删掉次模前提，取 $f(\{1\})=f(\{2\})=1,f(E)=3$，前缀差分可能产生 $(1,2)$，直接违反第二个单元素上界。这明确指出了可行性证明所需要的边际递减条件。