Блог

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

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

 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];
    }
  

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

смотрите эту ссылку в Википедии

выдержка:

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

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

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

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

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

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

Например: T (n) = 0, если n<1 или T (n-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);
}