Смена монеты - ошибка Java, пример 3
Проблема: вам выдаются монеты разного достоинства и общей суммы денег. Напишите функцию для вычисления наименьшего количества монет, необходимого для получения этой суммы. Если эта сумма не может быть получена какой-либо комбинацией монет, верните -1.
Пример 1:
Ввод: монеты = [1, 2, 5], сумма = 11. Выход: 3 Пояснение: 11 = 5 + 5 + 1
Пример 2:
Ввод: монеты = 2, сумма = 3 Выход: -1
You may assume that you have an infinite number of each kind of coin.
Мой код:
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
int new_amount=amount;
int count_coin=0;
int q=0,r=0,a=0;
int k=coins.length-1;
while(amount>0 && k>=0) {
q = new_amount / coins[k];
count_coin = count_coin + q;
r = new_amount % coins[k];
new_amount=r;
a+=q*coins[k];
k--;
}
if (a==amount){
return count_coin;
}
else{
return -1;
} }
Мой код хорошо работает для данных двух примеров. После работы с этим примером я взял еще один тестовый пример.
Пример 3. Ввод: монеты = [186 419,83 408], сумма = 6249 Выход: 20 Мой результат: -1
Я не понимаю этого примера. Если у кого-то есть представление об этом примере или о любом другом лучшем алгоритме, помимо моего, поделитесь им со мной.
Вижу ссылку Обмен монет (динамическое программирование). Но не могу понять.
Я также изучал Почему алгоритм жадной смены монет не работает для некоторых наборов монет? , но не могу понять, что он пытается сказать, поэтому я поднял этот вопрос.
Заранее спасибо.
Возможный дубликат Почему алгоритм жадной смены монет не работает для некоторых наборов монет?
Ответы 1
В вашем коде используется подход жадный, который не работает должным образом для произвольных номиналов монет (например, набор 3,3,4 не может дать ответ 6)
Вместо этого используйте подход динамическое программирование (пример)
Например, сделать массив A длины amount+1, заполнить его нулями, создать A[0] = 1 и пройти массив для каждого номинала монеты от n-й записи вниз, выбирая лучший результат для каждой ячейки.
Псевдокод:
for (j=0; j < coins.length; j++) {
c = coins[j];
for (i=amount; i >= c; i--){
if (A[i - c] > 0)
A[i] = Min(A[i], A[i - c] + 1);
}
}
result = A[amount] - 1;
Но сначала я сортирую номинал. Так что теперь у них порядок, а не произвольный.
как сортировка помогает в этом случае? @ Шифрование?
После сортировки сначала берется максимальный номинал, затем остальная сумма корректируется с учетом 2-го максимального достоинства.
@Encipher итак, [3,3,4] и 6, после первой итерации вы получите [3,3] и 2 -> тогда?
@Encipher Greedy + Sorting действительно работает для некоторых наборов, например, степени двойки, для системы монет в большинстве стран, но не работает в общем случае. Посмотри на мой пример. Выбор 4 перекрывает путь к лучшему ответу 3+3
хм, вот в чем проблема.
@ Сумма шифрования изменится. Также исправлено направление петли на i--
c - номинал монеты, поэтому для вашего примера он имеет значения `1,2,5
Допустим, у вас есть 3 и 5 в массиве монет. И сумма равна 6, тогда вы всегда будете сначала выбирать 5, после того, как это количество будет 1. Используйте рекурсивную функцию и попробуйте вернуться назад.