硬币找零的贪心算法c++

Question

所以，我正在创建一个硬币找零算法，它采用值 N 和任意数量的面额，如果它没有 1，我必须自动包含 1。我已经这样做了，但是现在有一个缺陷，我有 2 个矩阵，我需要使用其中的 1 个。是否可以重写 S[i] 矩阵并仍然增加数组的大小...。另外，我如何找到最大面额和第二高面额，然后一直到最小面额？我应该按照从高到低的顺序进行排序以使其更容易，还是有一种更简单的方法可以一个接一个地查找它们？

int main()
{
    int N,coin;
    bool hasOne;
    cout << "Enter the value N to produce: " << endl;
    cin >> N;
    cout << "Enter number of different coins: " << endl;
    cin >> coin;

    int *S = new int[coin];

    cout << "Enter the denominations to use with a space after it" << endl;
    cout << "(1 will be added if necessary): " << endl;
    for(int i = 0; i < coin; i++)
    {
        cin >> S[i];
        if(S[i] == 1)
        {
            hasOne = true;
        }
        cout << S[i] << " ";
    }
    cout << endl;
    if(!hasOne)
    {
        int *newS = new int[coin];
        for(int i = 0; i < coin; i++)
        {
            newS[i] = S[i];
            newS[coin-1] = 1;
            cout << newS[i] << "  ";
        }
        cout << endl;
        cout << "1 has been included" << endl;
    }

    //system("PAUSE");
    return 0;
}

Answer 1

你可以用std::vector来实现，那你只需要用push_back.

std::sort可以用来对面额进行降序排列，那么只需要检查最后一个是否是1，如果缺少则添加。（此代码中缺少很多错误检查，例如，您可能应该检查没有面额 >= 0，因为您使用的是有符号整数）。

#include <iostream>   // for std::cout/std::cin
#include <vector>     // for std::vector
#include <algorithm>  // for std::sort

int main()
{
    std::cout << "Enter the value N to produce:\n";
    int N;
    std::cin >> N;

    std::cout << "Enter the number of different denominations:\n";
    size_t denomCount;
    std::cin >> denomCount;

    std::vector<int> denominations(denomCount);
    for (size_t i = 0; i < denomCount; ++i) {
        std::cout << "Enter denomination #" << (i + 1) << ":\n";
        std::cin >> denominations[i];
    }

    // sort into descending order.
    std::sort(denominations.begin(), denominations.end(),
        [](int lhs, int rhs) { return lhs > rhs; });

    // if the lowest denom isn't 1... add 1.
    if (denominations.back() != 1)
        denominations.push_back(1);

    for (int coin: denominations) {
        int numCoins = N / coin;
        N %= coin;
        if (numCoins > 0)
            std::cout << numCoins << " x " << coin << '\n';
    }

    return 0;
}

现场演示：http://ideone.com/h2SIHs

硬币找零的贪心算法c++

Greedy Algorithm for coin change c++

c++

algorithm

greedy

coin-change