Жадный алгоритм для смены монет 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

Вы могли бы реализовать его с станд :: вектор, то вам нужно использовать только 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