минимальное количество монет для внесения изменений

Question

Я пытаюсь напечатать минимальное количество монет, чтобы внести изменения, если это невозможно. Print -1

В этой кодовой переменной int [] c (массив монет) есть номиналы, которые я могу использовать, чтобы подойтис общей суммой.

int total имеет общую сумму, которая мне нужна для использования монет (неограниченное количество)

    public static int mincoinDP(int[] c, int total) {
        int[][] a = new int[c.length + 1][total + 1];

        for (int i = 0; i <= c.length; i++) {
            a[i][0] = 0;
        }
        for (int j = 1; j <= total; j++) {
            a[0][j] = Integer.MAX_VALUE - total;
        }

        for (int i = 1; i <= c.length; i++) {
            for (int j = 1; j <= total; j++) {
                if (c[i - 1] > j) {
                    a[i][j] = Integer.MAX_VALUE - total;
                } else {
                    a[i][j] = Math.min(a[i - 1][j], 1 + a[i][j - c[i - 1]]);
                }
            }
        }

        return a[c.length][total];
    }

Для суммы: 4759 и массива: {31 90 8 36} Правильновывод: 59 Мой вывод: 60

Что не так в коде?

Ниже мое рекурсивное решение, пытающееся применить ту же логику в решении DP.Здесь что-то не так в логике.Для того же ввода он печатает -2147483595

    public static void main(String[] args) {
        int[] array = new int[] {31, 90, 8, 36};
        System.out.println(mincoin(array, 4759, 0));
    }

    public static int mincoin(int[] c, int total, int i) {

        if (total == 0) return 0;
        if (i >= c.length) return Integer.MAX_VALUE;


        int x = Integer.MAX_VALUE, y = Integer.MAX_VALUE;

        if (total - c[i] >= 0) {
            x = 1 + mincoin(c, total - c[i], i);
        }
        y = mincoin(c, total, i + 1);

        return Math.min(x, y);
    }

Редактировать: Проблемы в коде были:

1. Версия DP: если (c [i -1]> j), это случайкогда решение не возможно выбрать эту монету: Здесь мы должны принять решение без этой монеты, которая является [i-1] [j]
2. Рекурсивная версия: если (i> = c.length), она заканчиваетсяусловие, когда у нас нет монеты в этой позиции, здесь мы должны вернуть бесконечность (Integer.MAX_VALUE) и избежать целочисленного переполнения return Integer.MAX_VALUE - всего.

Хотя мне не нравится эта версия бесконечности,но не вижу здесь ничего хорошего, кроме этого.

Answer 1

Похоже, вы используете динамическое программирование, где a[i][j] предназначено для представления минимального количества монет (с использованием первых номиналов i), которое составляет j.Но я думаю, что ваши рецидивирующие отношения разорваны.Они должны быть:

a[0][j] = 0 if j==0, otherwise infinity

a[i][j] = a[i-1][j] if c[i-1] > j
a[i][j] = min(a[i-1][j], 1 + a[i][j-c[i-1]]) if c[i-1] <= j

Основная ошибка - это случай if c[i-1] > j в вашем коде.Вы устанавливаете значение на бесконечность (или ваш вариант бесконечности), но вам просто нужно скопировать минимальное количество монет из предыдущей строки, поскольку вы можете построить общее количество, используя меньшее количество монет.

Кстати, есть более аккуратный способ написания этого кода.В псевдокоде:

a = new int[total+1]
for int j = 1 to total+1 {
    a[j] = infinity
}
for int coin in coins {
    for j = coin to total+1 {
        a[j] = min(a[j], a[j-coin]+1)
    }
}

По сути, это тот же алгоритм, но он использует меньший одномерный массив, который он модифицирует на месте.