Изменение монеты - Java не прошла пример 3

Question

Проблема: Вам выдаются монеты разных номиналов и общая сумма денег. Напишите функцию, чтобы вычислить наименьшее количество монет, которое вам нужно, чтобы составить эту сумму. Если эта сумма денег не может быть составлена ​​какой-либо комбинацией монет, верните -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

Я не понимаю этого примера. Если у кого-то есть идеи по поводу этого примера или любого другого лучшего алгоритма, кроме моего, поделитесь им со мной.

Я вижу Смена монеты (динамическое программирование) ссылка. Но не могу понять.

Я также изучал Почему алгоритм жадных монет не работает для некоторых наборов монет? но не могу понять, что он пытается сказать. Итак, я поднял этот вопрос.

Заранее спасибо.

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