Восходящий подход к минимальному количеству монет для обмена
Я строю подход снизу вверх к проблеме смены монет. Я должен дать минимальное количество монет, необходимое для выдачи запрошенного изменения. Может быть возможно, что изменение не может быть дано, потому что данные номиналы не могут формировать значение.
Например, если заданы номиналы {4, 8}, и они требуют изменения 5, тогда невозможно дать 5. Я построил программу ниже, и она работает хорошо для большинства ситуаций, если невозможно сформировать запрошенное изменение , Например, когда номиналы просто {4}, а я запрашиваю 5, он возвращает одно, которое является ложным. Что я могу сделать, чтобы исправить эту проблему?
Здесь P представляет запрошенное изменение,
S — количество конфессий, хранящихся в массиве denominations [] от индекса 0 до S — 1. dp — двумерный массив для вычисления, инициализированный -1.
for (int i = 0; i <= P; ++i) {
for (int j = 0; j < S; ++j) {
int ans, x, y;
// Min. no. of coins with current coin
x = (i - denominations[j] >= 0) ? dp[i - denominations[j]][j] + 1: 0;
// Min. no. of coins w/o current coin
y = (j > 0) ? dp[i][j - 1] : 0;
ans = min(x, y);
if (ans == 0) ans = max(x, y);
dp[i][j] = ans;
}
}
Спасибо за помощь.
Решение
Ошибка в том, что вы неправильно обрабатываете случай, когда это запрещено и то и другое использовать текущую монету, а также не использовать это. Это происходит в вашем примере, например: когда i = 1 и j = 0, мы пытаемся получить всего 1c, не используя ничего или просто монету 4c; но мы не можем сделать это с монетой 4c, и мы также не можем сделать это без монеты 4c.
В таких случаях и x, и y будет присвоен 0, а строка if (ans == 0) ans = max(x, y);, который призван поймать тот случай, когда или из возможностей запрещены, неправильно назначается 0 для ans. Последующие итерации внешнего цикла, следовательно, «подумают», что можно сделать соответствующую сумму на сумму, в которой нет монет, и безболезненно прибавить 1 к этому, давая неправильный ответ 1 для вашего примера.
Я думаю, что самое простое решение — выбрать другое значение часового, отличное от 0, чтобы обозначить «Это действие невозможно и не должно рассматриваться». Поскольку вы объединяете два возможных действия с min(), чрезвычайно высокое значение подходит естественно:
#define INF (INT_MAX-1) // Or anything higher than the biggest sensible answer
for (int i = 0; i <= P; ++i) {
for (int j = 0; j < S; ++j) {
int ans, x, y;
// Min. no. of coins with current coin
x = (i - denominations[j] >= 0) ? min(INF, dp[i - denominations[j]][j] + 1) : INF;
// Min. no. of coins w/o current coin
y = (j > 0) ? dp[i][j - 1] : INF;
ans = min(x, y);
dp[i][j] = ans;
}
}
Обратите внимание, как линия ans = min(x, y); теперь дает правильный ответ без дальнейшей работы, в том числе и в том случае, когда он должен быть INF потому что и х и у INF,
Более тонкий момент заключается в том, что когда мы читать немного dp[a][b] во время наших расчетов, это значение может быть INF: это законное значение, указывающее, что a центы не могут быть сделаны с любой комбинацией монет типа <знак равно b, В идеале, значение, выбранное для INF будет иметь свойство, что добавление или умножение его на любое положительное значение оставляет его в INFс тех пор нам не нужно будет вносить дальнейшие изменения в этот алгоритм: каждая операция, которую мы выполняем на INF значение будет правильно оставить его в INF, Но целочисленная арифметика не работает таким образом, поэтому после добавления чего-либо к значению, которое может быть INF нам нужно проверить, что мы не «прошли бесконечность» и исправить это, если так: вот почему d[i - denominations[j]][j] + 1 завернут в min(INF, ...) вызов. (Это также почему я определил INF быть на один меньше, чем INT_MAX — так что переполнение не может произойти.)
Другие решения