贪婪算法

一种用于从尽可能小的组成部分递归构造对象集合的算法。

给定一个 集合 的 个整数 (, , ..., )，其中 ，可以使用贪婪算法找到系数的向量 (, , ..., ) 使得

(1)

其中 是点积，对于给定的整数 。这可以通过令 对于 , ..., 并设置

(2)

其中 是向下取整函数。现在定义表示与 之间的差为

(3)

如果在任何步骤 ，则已找到表示。否则，递减具有最小 的非零 项，将所有 设置为 ，并从以下项构建剩余项

(4)

对于 , ..., 1 直到 或所有可能性都已用尽。

例如，麦乐鸡块数是只能使用 表示的数字。取 并迭代应用该算法得到序列 (0, 0, 3), (0, 2, 2), (2, 1, 2), (3, 0, 2), (1, 4, 1)，此时 。因此 62 是一个麦乐鸡块数，其中

(5)

如果任何 整数 可以使用序列 (, , ...) 以 或 1 表示，则此序列称为完全序列。

贪婪算法也可用于在有限的步骤内将任意分数分解为埃及分数。对于分数 ，找到最小的整数 使得 ，即，

(6)

其中 是向上取整函数。然后找到最小的整数 使得 。迭代直到没有余数。对于 和 ，该算法给出两个或更少的项；对于 ，给出三个或更少的项；对于 ，给出四个或更少的项。