Неполадки при печати наименований, используемых в алгоритме Minimum Change

Поэтому я написал рекурсивный алгоритм для задачи определения наименьшего количества "монет" определенного набора конфессий, которые можно получить для данной суммы. Кажется, что алгоритм работает, но, поскольку он рекурсивный и рассчитывает все возможные варианты, прежде чем выбрать один или другой, мне сложно найти способ распечатать используемые купюры. По сути, я могу рассчитать наименьшее количество монет, которые можно использовать, но не то, какие это монеты. Вот код и маленький основной метод, который я использую для управления им. Любые предложения по оптимизации самого алгоритма также приветствуются.

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);
        }
    }
}
Источник

2 ответа

Решение

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

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

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

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

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 должен содержать список монет, выбранных в хронологическом порядке.

Источник

Задача минимального изменения не должна программироваться рекурсивно. Это может быть запрограммировано более простым итеративным способом.

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].

Источник
Другие вопросы по тегам