Динамическое программирование монет Изменить Проблемы

Question

У меня возникают проблемы с пониманием динамического программирования решения различных проблем, в частности проблемы изменения монеты:

«Учитывая значение N, если мы хотим внести изменения в N центов, и мы имеем бесконечная подача каждой из S = {S1, S2, .., Sm} ценных монет, сколько способов сделать это изменение? Порядок монет не имеет значения.

Например, для N = 4 и S = {1,2,3}, существует четыре решения: {1,1,1,1}, {1,1,2}, {2,2}, {1,3}, поэтому выход должен быть равен 4 Для N = 10 и S = ​​{2, 5, 3, 6} существует пять решений: {2,2,2,2,2}, {2,2,3,3}, {2,2, 6}, {2,3,5} и {5,5}, поэтому выход должен быть 5. "

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

Эти проблемы выглядят очень похожими, но решения очень разные.

Количество возможных способов внесения изменений: оптимальная субструктура для этого: DP (m, n) = DP (m-1, n) + DP (m, n-Sm) где DP - это число решения для всех монет до m-й монеты и суммы = n.

Минимальное количество монет: оптимальная подструктура для этого является DP [I] = {Мин DP [я-d1], DP [я-d2], ... DP [я-дп]} + 1 где i - общая сумма, а d1..dn - номинал каждой монеты.

Почему первый требует 2-мерного массива, а второй - 1-мерного массива? Почему оптимальная субструктура для количества способов внесения изменений не "DP [i] = DP [i-d1] + DP [i-d2] + ... DP [i-dn]", где DP [i ] - количество способов, которыми я могу получить монеты. Это звучит логично для меня, но вызывает неправильный ответ. Почему это второе измерение для монет, необходимых в этой проблеме, но не необходимое в проблеме минимального количества?

ССЫЛКИ НА ПРОБЛЕМЫ:

http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

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

Answer 1

1. Позволяет первый разговор о количестве путей, ДП (т, п) = DP (м-1, п) + DP (м, н-Sm). Это действительно правильно, потому что либо вы можете использовать mth деноминацию, либо вы можете избежать этого. Теперь вы говорите, почему мы не пишем его как DP [i] = DP [i-d1] + DP [i-d2] + ... DP [i-dn]. Ну, это приведет к перерасчету, давайте возьмем пример, где n = 4 m = 2 и S = ​​{1,3}. Теперь согласно вашему решению dp [4] = dp [1] + dp [3]. (Предполагая, что 1 является базовым случаем dp [1] = 1). Теперь dp [3] = dp [2] + dp [0]. (Снова dp [0] = 1 по основному случаю). Снова применяя тот же dp [2] = dp [1] = 1. Таким образом, в итоге вы получаете ответ как 3, когда он должен быть всего 2 ((1,3) и (1,1,1,1)). Так как ваш второй метод рассматривает (1,3) и (3,1) как два разных решения. Ваш второй метод может быть применен к случаю, когда имеет значение порядок, что также является стандартной проблемой.

2. Теперь, к вашему второму вопросу, вы говорите, что минимальное количество наименований может быть обнаружено DP [i] = Мин {DP [i-d1], DP [i-d2], ... DP [i -dn]} + 1.Ну, это правильно, так как при поиске минимальных наименований, порядка или никакого заказа не имеет значения. Почему это линейный/1-D DP, хорошо, хотя массив DP равен 1-D, каждое состояние зависит от не более m состояний, в отличие от вашего первого решения, где массив является 2-D, но каждое состояние зависит не более чем от двух состояний. Таким образом, в обоих случаях время выполнения, которое (количество состояний * число состояний зависит от каждого состояния), равно O (нм). Итак, оба правильные, просто ваше второе решение сохраняет память. Таким образом, либо вы можете найти его методом 1-D-массива, либо двумерным путем использования повторения dp (n, m) = min (dp (m-1, n), 1 + dp (m, n-Sm)). (Просто используйте мин при первом повторении)

   
   Надеюсь, что я очистил сомнения, сделайте сообщение, если еще что-то неясно.

Answer 2

This - очень хорошее объяснение проблемы с изменением монет с помощью динамического программирования.

код выглядит следующим образом:

public static int change(int amount, int[] coins){ 
    int[] combinations = new int[amount + 1]; 

    combinations[0] = 1; 

    for(int coin : coins){ 
     for(int i = 1; i < combinations.length; i++){ 
      if(i >= coin){ 
       combinations[i] += combinations[i - coin]; 
       //printAmount(combinations); 
      } 
     } 
     //System.out.println(); 
    } 

    return combinations[amount]; 
}