Блог

Главная - Вопросы по программированию - Алгоритм смены монет всегда возвращает единицу

Алгоритм смены монет всегда возвращает единицу

#java #recursion #dynamic-programming #coin-change

#java #рекурсия #динамическое программирование #смена монет

Вопрос:

 /**
 * 
 * @param d
 *            currency divisions
 * @param p
 *            target
 * @return number of coins
 */
public static int change(int[] d, int p) {
    int[] tempArray = new int[p*2]; // tempArray to store set
                                                    // of coins forming
                                                    // answer
    for (int i = 1; i <= p; i  ) { // cycling up to the wanted value
        int min = Integer.MAX_VALUE; //assigning current minimum number of coints
        for (int value : d) {//cycling through possible values
            if (value <= i) {
                if (1   tempArray[i - value] < min) { //if current value is less than min
                    min = 1   tempArray[1 - value];//assign it
                }
            }
        }
        tempArray[i] = min; //assign min value to array of coins
    }
    return tempArray[p];
}

Кто-нибудь может помочь мне понять, почему это не работает, пожалуйста? Метод предназначен для ввода значений, представляющих монеты, он имеет бесконечное количество этих монет, с помощью которых можно сформировать целое число p, метод должен возвращать минимальное количество монет, используемых для получения p.

Ответ №1:

tempArray инициализируется значением 0 для всех индексов. использование tempArray[1-value] в основном дает вам 0. Итак, все индексы от 1 до p имеют значение 1 tempArray[1-значение] Это 1. Кроме того, tempArray[1-значение] является отрицательным индексом. Я думаю, вы имели в виду tempArray[i-value]

Комментарии:

1. Блестяще, я только что изменил строку, которую вы упомянули, с 1-value на i-value, и это работает. Как вы думаете, теперь это правильно? Я действительно сбит с толку тем, что на самом деле происходит строка за строкой, не могли бы вы, пожалуйста, дать мне краткий обзор?

2. Он постепенно проверяет каждое целое число от 1 до p, минимальное количество номиналов, необходимое для получения значения, если вы хотите знать, сколько монет номиналом {1,2,3,4} вам понадобится, чтобы в общей сложности получилось 10. код начинается с 1, проверяет минимальное количество необходимых монет, затем для 2, затем для 3 и так далее. Вы могли бы рассматривать это как разделение 10 на 4 4 2 , при 4 значение равно 1, при 8 значение равно 2 и, наконец, при 10 значение равно 3. Вы можете увидеть, что происходит, напечатав значения min в конце каждой итерации

Метки: