貪婪演算法

一種用於從儘可能小的組成部分遞迴構造物件集合的演算法。

給定一個 集合 的 個整數 (, , ..., )，其中 ，可以使用貪婪演算法找到係數的向量 (, , ..., ) 使得

(1)

其中 是點積，對於給定的整數 。這可以透過令 對於 , ..., 並設定

(2)

其中 是向下取整函式。現在定義表示與 之間的差為

(3)

如果在任何步驟 ，則已找到表示。否則，遞減具有最小 的非零 項，將所有 設定為 ，並從以下項構建剩餘項

(4)

對於 , ..., 1 直到 或所有可能性都已用盡。

例如，麥樂雞塊數是隻能使用 表示的數字。取 並迭代應用該演算法得到序列 (0, 0, 3), (0, 2, 2), (2, 1, 2), (3, 0, 2), (1, 4, 1)，此時 。因此 62 是一個麥樂雞塊數，其中

(5)

如果任何 整數 可以使用序列 (, , ...) 以 或 1 表示，則此序列稱為完全序列。

貪婪演算法也可用於在有限的步驟內將任意分數分解為埃及分數。對於分數 ，找到最小的整數 使得 ，即，

(6)

其中 是向上取整函式。然後找到最小的整數 使得 。迭代直到沒有餘數。對於 和 ，該演算法給出兩個或更少的項；對於 ，給出三個或更少的項；對於 ，給出四個或更少的項。