Восходящий подход к минимальному количеству монет для обмена

Question

Я строю подход снизу вверх к проблеме смены монет. Я должен дать минимальное количество монет, необходимое для выдачи запрошенного изменения. Может быть возможно, что изменение не может быть дано, потому что данные номиналы не могут формировать значение.

Например, если заданы номиналы {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;
    }
}

Спасибо за помощь.

Answer 1

Ошибка в том, что вы неправильно обрабатываете случай, когда запрещено использовать текущую монету и не использовать ее. Это происходит в вашем примере, например: когда 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 - так что переполнение не может произойти.)