Жадный алгоритм замены монет Переполнение стека

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;
}

-1

algorithm c++coin-change greedy

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вы можете реализовать это с помощью 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

1