有效率的贏家決定機制

greedy(貪婪)這個字眼一般而言是負面的，不過用在演算法設計時，並不伴隨有任何道德評價(這並非意味電腦科學家沒有道德標準)，而僅僅代表某種解題策略。具體而言，如果一個問題的最佳解需關照全貌才能得知，貪婪演算法會設法將其分階段求解，將每一個階段最好的解答集合起來成為整個問題的解。

貪婪演算法不見得能找到問題的最佳解，但它的價值在於能夠快速解題。以圖中的組合拍賣為例。我們有A, B, C, D, E五項物品要進行拍賣，每項物品只有一件，且有P1 ~ P5五位投標者，每位投標者的標金(bid)及想要的物品組合(bundle)已顯示在圖中。我們假設投標者均是single-minded (不妥協的)，即不接受只給他部分物品的結果。例如P2要A, B, C三項物品，願意出54元，如果結果是分配給P2 A, B兩項，就算只要P2付40元，P2也是不會接受的。換句話說，他們不會有「沒魚蝦也好」這種心態。

在上述情形下，要找出能夠使得贏家標金總和最高的贏家組合，是一個weighted set cover問題。這個問題是一個NP-Hard問題，沒有甚麼有效率的演算法。如果先把所有可能的贏家組合列出來，再找尋其中的最佳組合(如圖中所列的那樣)。這屬於暴力作法，時間法複雜度可是嚇人的O(2^n)。

這裡就有一個貪婪的演算法。我們先計算每位投標者投標金額除以所投標物品的數量，當作投標者的性價比，然後從性價比最高的投標者開始挑選，如果投標者需求的物品尚未配置出去，就配置給該投標者，否則就跳過此投標者。

在我們的例子中，P4的性價比70/2=35是所有投標者最高的，所以配給P4所要的DE兩項物品。性價比次高的為P3 (93/3=31)，但P3所需求的BDE無法如數配給(DE已分配給P4)，所以跳過P3。性價比再其次的為P1 (63/3=21)，其所需求的ACD一樣無法如數配給。第四個考慮的是P2，他所需求的ABC可以配置沒有問題。最後的贏家組合就是P4和P2。

不過，這種組合拍賣問題的精隨並不在找出贏家組合(雖然找出贏家組合的時間複雜度的確是個問題)，而是決定每位贏家該付多少價錢的訂價策略(pricing strategy)。此策略須使得所有投標者有動機誠實出價。以臨界值(critical value)的訂價策略為例，贏家所應付的價錢，是(在所有其他投標者標金不變的前提下)仍能使該贏家不會輸掉拍賣的最小標金。這個定價策略的基本精神其實與second-price auction類似。在我們的例子中，P2應該付42元而P4應該付62元。