Выявление ошибок в наименованиях, используемых в алгоритме с минимальным изменением

Question

Итак, я написал рекурсивный алгоритм для решения вопроса о наименьшем числе «монет» определенного набора наименований, доступных для получения данной суммы. Алгоритм, похоже, работает, но поскольку он рекурсивный и вычисляет все возможные варианты, прежде чем выбирать один или другой, у меня возникло трудное время, когда вы можете распечатать используемые купюры. Поэтому я могу рассчитать наименьшее количество монет, которые можно использовать, но не , которые монеты они. Вот код и маленький основной метод, который я использую для его вождения. Также приветствуются любые предложения по оптимизации самого алгоритма.

public class DynamicCoinChange { 

    public static void main(String[] args) { 
     int[] denoms = {1, 6, 10, 25}; 
     int numCoins = dynamicCoinChange(denoms, 18, 3); 
     System.out.println(numCoins); 
    } 

    public static int dynamicCoinChange(int[] denoms, int amt, int start) { 
     if (amt == 0 || start < 0) { 
      return 0; 
     } else if (amt == 1) { 
      return 1; 
     } else if (denoms[start] > amt || 
       dynamicCoinChange(denoms, amt, start-1) < 
       (1 + dynamicCoinChange(denoms, amt-denoms[start], start)) && 
       !(dynamicCoinChange(denoms, amt, start-1) == 0)) { 
      return dynamicCoinChange(denoms, amt, start-1); 
     } else { 
      return 1 + dynamicCoinChange(denoms,amt-denoms[start], start); 
     } 
    } 
} 

Answer 1

Нам нужно знать две части информации:

• когда монета выбрана для оптимального решения
• который монета была выбрана для оптимального решения

По вашему алгоритму, мы знаем, что мы выбираем монету, когда вы возвращаете 1. Мы также знаем, что выбранная монета, при которой выбранный индекс выбранной монеты равен start. Таким образом, у нас есть информация для решения этой проблемы.

Поскольку производительность здесь не проблема, мы просто передадим параметр монет, который будет заполнен, когда будут выбраны монеты.

public static int dynamicCoinChange(int[] denoms, int amt, int start, ArrayList<Integer> coins) { 
    if (amt == 0 || start < 0) { 
     return 0; 
    } else if (amt == 1) { 
     coins.add(1); 
     return 1; 
    } else if (denoms[start] > amt 
      // Note that these calls are not guaranteed to be in our solution 
      // Thus, we make a copy to prevent the calls from modifying our solution 
      || dynamicCoinChange(denoms, amt, start-1, new ArrayList<Integer>(coins)) < 
       (1 + dynamicCoinChange(denoms, amt-denoms[start], start, new ArrayList<Integer>(coins))) 
      && !(dynamicCoinChange(denoms, amt, start-1, new ArrayList<Integer>(coins)) == 0)) { 
     return dynamicCoinChange(denoms, amt, start-1, coins); 
    } else { 
     coins.add(denoms[start]); 
     return 1 + dynamicCoinChange(denoms,amt-denoms[start], start, coins); 
    } 
} 

Поскольку это требует, чтобы мы изменили наш метод подписи, мы также должны изменить наш водитель:

public static void main(String[] args) { 
    int[] denoms = {1, 6, 10, 25}; 
    ArrayList<Integer> coins = new ArrayList<Integer>(); 
    int numCoins = dynamicCoinChange(denoms, 7, 3, coins); 
    for (Integer coin : coins) 
     System.out.println(coin); 
    System.out.println(numCoins); 
} 

В конце рекурсивных вызовов, coins должен содержать перечень монет, выбранных в хронологическом порядке ,

Answer 2

Проблема минимального изменения не обязательно должна быть запрограммирована рекурсивно. Его можно запрограммировать более простым итерационным способом.

int[] denoms = { 1, 6, 10, 25 }; 
int amt = 18; 
double[] min = new double[ amt + 1 ]; 

for(int i = 1; i < min.length; i++) { // We're keeping min[ 0 ] as 0/ 
    min[ i ] = Double.POSITIVE_INFINITY; 
} 

for(int i = 1; i <= amt; i++) { 

    for(int j = 0; j <= N - 1; j++) { 

     if(denoms[ j ] <= i && min[ i - denoms[ j ] ] + 1 < min[ i ]) 
      min[ i ] = min[ i - denoms[ j ] ] + 1; 

    } 
} 

Здесь ваше решение будет входить min [amt].