形式陈述

在有限拟阵 $M=(E,\mathcal{I})$ 上给元素任意实权重，按权重非增扫描；若把元素 $e$ 加入当前集合仍独立，就接受它。扫描结束所得极大独立集是一组基，拟阵贪心定理保证它是最大权基。若目标改为最大权独立集而不要求成为基，则应跳过负权元素；在非负权情形下两种目标兼容。证明使用交换公理：把贪心基按次序与任一最优基对齐，每步用权重不低于被替换元素的贪心元素完成交换。反过来，一个有限独立系统对所有非负权重都被该算法正确求出最大权独立集，当且仅当它是拟阵。

直觉

拟阵交换公理保证“当前最好的可行元素”不会把未来堵死：任何另一个完整方案都能逐步交换成包含贪心选择且不增加损失。

例子与边界

图拟阵中独立集是森林；按边权非增扫描得到最大权生成树。通常所称的 Kruskal 最小生成树算法采用最小权版本，按边权非减扫描，或等价地在固定基大小下对权重取负。线性拟阵中独立性是向量线性无关，可贪心选最大权基。普通背包可行集不是拟阵；高价值重量比贪心会失败。定理依赖同一个拟阵上的加性元素权重，不自动覆盖次模目标、交两个拟阵或带容量的复杂约束。

推论与应用

该算法统一解释最小生成树、向量基选择和调度中的贪心正确性，并提供检验某类可行系统能否被简单权重排序完全解决的结构标准。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。