自動售票機

第一個簡單示例：

你有一個自動售票機，可以交換硬幣值 1,2,5,10 和 20.交換的分配可以看作是一系列硬幣掉落，直到分配出正確的價值。我們說當它的硬幣計數值很小時，它是最優的。 ****

讓 [1,50] 中的 M 成為 T 中的 T 和 P 的價格，有人為 T 支付的錢，P >= M。讓 D=P-M。我們定義了一個步驟的好處，作為 D 和 D-c 之間的差異，c 是自動機在此步驟中分配的硬幣。

交換的貪婪技術是以下偽演算法方法：

步驟 1： D > 20 分配 20 個硬幣並設定 D = D - 20
步驟 2： D > 10 分配 10 個硬幣並設定 D = D - 10
步驟 3： D > 5 分配 5 個硬幣並設定 D = D - 5
步驟 4： D > 2 分配 2 個硬幣並設定 D = D - 2
步驟 5 ： 雖然 D > 1 分配 1 個硬幣並設定 D = D - 1

之後所有硬幣的總和顯然等於 D。它是一種**貪婪的演算法，**因為在每個步驟之後以及在每次重複步驟之後，效益最大化。我們不能分配另一個具有更高利益的硬幣。

現在票證自動作為程式（在 C++中）：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// read some coin values, sort them descending,
// purge copies and guaratee the 1 coin is in it
std::vector<unsigned int> readInCoinValues();

int main()
{
    std::vector<unsigned int> coinValues;   // Array of coin values ascending    
    int ticketPrice;                        // M in example
    int paidMoney;                          // P in example

    // generate coin values
    coinValues = readInCoinValues();
    
    cout << "ticket price: ";
    cin >> ticketPrice;
    
    cout << "money paid: ";
    cin >> paidMoney;
    
    if(paidMoney <= ticketPrice)
    {
        cout << "No exchange money" << endl;
        return 1;
    }
    
    int diffValue = paidMoney - ticketPrice;
    
    // Here starts greedy

    // we save how many coins we have to give out
    std::vector<unsigned int> coinCount;
    
    for(auto coinValue  = coinValues.begin();
             coinValue != coinValues.end(); ++coinValue)
    {
        int countCoins = 0;
        
        while (diffValue >= *coinValue)
        {
            diffValue -= *coinValue;
            countCoins++;
        }
        
        coinCount.push_back(countCoins);
    }
    
    // print out result
    cout << "the difference " << paidMoney - ticketPrice 
         << " is paid with: " << endl;
    
    for(unsigned int i=0; i < coinValues.size(); ++i)
    {
        if(coinCount[i] > 0)
            cout << coinCount[i] << " coins with value " 
                 << coinValues[i] << endl;
    }
    
    return 0;
}

std::vector<unsigned int> readInCoinValues()
{
    // coin values
    std::vector<unsigned int> coinValues;
    
    // make sure 1 is in vectore
    coinValues.push_back(1);

    // read in coin values (attention: error handling is omitted)
    while(true)
    {
        int coinValue;
        
        cout << "Coin value (<1 to stop): ";
        cin >> coinValue;
        
        if(coinValue > 0)
            coinValues.push_back(coinValue);
        
        else
            break;
    }
    
    // sort values
    sort(coinValues.begin(), coinValues.end(), std::greater<int>());
    
    // erase copies of same value
    auto last = std::unique(coinValues.begin(), coinValues.end());
    coinValues.erase(last, coinValues.end());
    
    // print array
    cout << "Coin values: ";
    
    for(auto i : coinValues)
        cout << i << " ";
    
    cout << endl;
    
    return coinValues;
}

請注意，現在有輸入檢查以保持示例簡單。一個示例輸出：

Coin value (<1 to stop): 2
Coin value (<1 to stop): 4
Coin value (<1 to stop): 7
Coin value (<1 to stop): 9
Coin value (<1 to stop): 14
Coin value (<1 to stop): 4
Coin value (<1 to stop): 0
Coin values: 14 9 7 4 2 1 
ticket price: 34
money paid: 67
the difference 33 is paid with: 
2 coins with value 14
1 coins with value 4
1 coins with value 1

只要 1 在我們現在的硬幣值中，演算法將終止，因為：

• D 每一步都嚴格降低
• D 永遠不會比同時最小的硬幣 1 小

但該演算法有兩個缺陷：

1. 讓 C 成為最大的硬幣價值。只要 D/C 是多項式，執行時只是多項式，因為 D 的表示僅使用 log D 位，並且執行時至少是線性的 D/C。
2. 在每個步驟中，我們的演算法選擇區域性最優。但這還不足以說該演算法找到了全域性最優解（請參閱此處或 Korte 和 Vygen的書中的更多資訊 ）。

一個簡單的反例：硬幣是 1,3,4 和 D=6。最佳解決方案顯然是兩個價值 3 的硬幣，但貪婪在第一步選擇 4，所以它必須在第二步和第三步選擇 1。所以它沒有提供最佳的選擇。該示例的可能的最佳演算法基於動態程式設計。