Начало динамического программирования - помощь в замене жадных монет

Question

В настоящее время я работаю над книгой по разработке алгоритмов и натолкнулся на вопрос, в соответствии с которым вы должны реализовать жадный алгоритм с динамическим программированием для решения проблемы замены монет.

Я пытался реализовать это, и я просто не могу понять или понять алгоритм, приведенный в моей книге. Алгоритм следующий (с моим (отсутствие) понимания в комментариях):

Change(p) {
  C[0] = 0
    for(i=1 to p) //cycling from 1 to the value of change we want, p
      min = infinity
        for(j=1 to k( //cyle from 1 to...?
          if dj <=i then
            if(1+C[i-dj] < min) then
               min = 1+C[i-dj]
            endif
          endif
        endfor
     C[i] = min
    endfor
  return C[p]
}

И моя попытка интерпретации происходящего:

/**
     * 
     * @param d
     *            currency divisions
     * @param p
     *            target
     * @return number of coins
     */
    public static int change(int[] d, int p) {
        int[] tempArray = new int[Integer.MAX_VALUE]; // 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
        }
        System.out.println("help"); // :(
        return tempArray[p];
    }

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

Answer 1

Немного опоздал на вечеринку, но ваша функция уже работает.

public static int change(int[] d, int p) {
    // tempArray to store set of coins forming answer
    int[] tempArray = new int[Integer.MAX_VALUE];

    tempArray[0] = 0; // INITIAL STEP MISSING

    for (int i = 1; i <= p; ++i) { // cycling up to the wanted value
        // assigning current minimum number of coins
        int min = Integer.MAX_VALUE;

        // cycling through possible values
        for (int value : d) {

            if (value <= i) { // FIX missing = in <=

                // if current value is less than min
                if (1 + tempArray[i - value] < min) {

                    // FIX, it's [i-value] not [1-value]
                    min = 1 + tempArray[i - value];
                }
            }
        }
        tempArray[i] = min; // assign min value to array of coins
    }
    return tempArray[p];
}

И используя его.

public static void main(String[] args) {
    int[] coins = new int[] { 25, 12, 10, 5, 1 };

    int coinCount = change(coins, 15);
    System.out.println("min change: " + coinCount);
}

Answer 2

Похоже, это проблема HW, поэтому я дам несколько советов. Первое, что нужно сделать, чтобы решить проблему с помощью DP, это «Думай, вернись и решай снизу вверх».

«Думай сверху вниз» - это та часть, где вы формулируете рекурсивное отношение

Для Eg: T (n) = 0, если n <1 или T (n-1) в противном случае; </p>

Рекурсивное отношение основывается на ранее вычисленных подзадачах.

«Решить снизу вверх» - это та часть, где ваш код решит проблему снизу вверх на основе найденной рекурсивной зависимости.

Обычно кодирование простое, и у более сложной части получается хорошее рекурсивное отношение (хотя рекурсии не будет).

Answer 3

см. ссылка на википедию

выдержка:

Свойство жадного выбора Мы можем сделать любой выбор, который покажется вам наилучшим, а затем решить подзадачи,возникать позже.Выбор, сделанный жадным алгоритмом, может зависеть от решений, сделанных до сих пор, но не от будущих решений или всех решений подзадачи.Итеративно делает один жадный выбор за другим, уменьшая каждую данную проблему в меньшую.Другими словами, жадный алгоритм никогда не пересматривает свой выбор.Это основное отличие от динамического программирования, которое является исчерпывающим и гарантированно найдет решение.После каждого этапа динамическое программирование принимает решения на основе всех решений, принятых на предыдущем этапе, и может пересмотреть алгоритмический путь предыдущего этапа к решению.

Ваш код повторяется по int p, чтобы получить оптимальный результатchoice и помещает его в массив tempArray, затем использует это значение для проверки оптимального выбора в следующей итерации.

Answer 4

Суть динамического программирования состоит в том, чтобы разбить проблемы на подзадачи, а затем начать строить решение вверх.Идея состоит в том, что если вы решите «n» подзадач, вы можете объединить их, и это будет решением всей проблемы.Рекурсия является примером динамического программирования, за исключением того, что она страдает от потенциальных проблем переполнения стека.Другой метод называется запоминанием, который кэширует результаты для более быстрого поиска, а не для пересчета уже вычисленных проблем.Это экономит много времени на обработку и ускоряет программу.Что касается проблемы с жадным изменением монеты, то суть в том, чтобы искать наибольшее номинал и использовать его до тех пор, пока он больше не может быть использован (т.е. делить общую сумму многократно на наибольшее номинал и отслеживать остаток), а затем перейти кследующий по величине и повторяйте тот же процесс, пока не останетесь с наименьшим количеством, которое может быть представлено наименьшим номиналом.Вы можете хранить минимальное значение в массиве и постоянно обновлять его, если найден новый минимум (т. Е. Запоминание).Я надеюсь, что люди могут исправить меня, если я где-то не прав.

РЕДАКТИРОВАТЬ: однако обратите внимание, что не все проблемы могут быть решены с помощью динамического программирования, и динамическое программирование не имеет ничего общего с любым языком программирования, вместо этого это просто имяметодика, используемая для решения задач оптимизации.