自动售票机

第一个简单示例：

你有一个自动售票机，可以交换硬币值 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。所以它没有提供最佳的选择。该示例的可能的最佳算法基于动态编程。