Проблема смены монет - грубое решение проблемы с возвратом, но как получить монеты? - PullRequest
Новая
       27

Проблема смены монет - грубое решение проблемы с возвратом, но как получить монеты?

0 голосов
/ 28 ноября 2018

У меня есть решение для грубой силы с возвратом, чтобы решить проблему с обменом монет.В настоящее время я получаю минимальное количество монет, которое можно использовать.Но как я могу вернуть монеты, которые были использованы?Так, например, если сумма равна 100, то я хотел бы вернуть [25, 25, 25, 25].

Мой текущий код ниже: 

public class Solution {

public static void main(String[] args) {
    Solution s = new Solution();

    int coinChange = s.coinChange(0, new int[] { 1, 25, 50 }, 100);
    System.out.println(coinChange);
}

public int coinChange(int idx, int[] coins, int amount) {
    if (amount == 0){
        return 0;
    }

    if (idx < coins.length && amount > 0) {
        int maxVal = amount / coins[idx];
        int minCost = Integer.MAX_VALUE;
        for (int x = 0; x <= maxVal; x++) {
            if (amount >= x * coins[idx]) {
                int res = coinChange(idx + 1, coins, amount - x * coins[idx]);
                if (res != -1)
                    minCost = Math.min(minCost, res + x);
            }
        }
        return (minCost == Integer.MAX_VALUE) ? -1 : minCost;
    }
    return -1;
}
}

1 Ответ

0 голосов
/ 28 ноября 2018

Прежде всего, я предлагаю использовать точные имена переменных.Это позволит всем, в том числе и вам самим, понять, как работает алгоритм.Ваш текущий массив "coins" - это не список монет, это список доступных купюр, поэтому он должен называться "denominations" или "denominations_available" или что-то в этом роде.Переменная, которую вы называете «сумма», представляет собой оставшуюся сумму, поэтому она должна называться либо «оставшаяся», либо сумма_ремонтная.список, который обрабатывается как стек. Например, вы можете использовать ArrayList of Integers. Каждый раз, когда вы вызываете coinChange, добавляйте номинал выбранной монеты (denominations [idx]) в свой список, прежде чем делать вызов. Каждый раз, когда вывернуть -1 (ошибка), удалить последний элемент в списке (если он есть) перед возвратом. Когда условие успеха будет достигнуто (amount_remaining == 0), список монет будет содержать используемые монеты.

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

int best_coin = 0;
for (int x = 0; x <= maxVal; x++) {
    if (amount >= x * coins[idx]) {
        <<<<<< PUSH GOES HERE
        int res = coinChange(idx + 1, coins, amount - x * coins[idx]);
        <<<<<< POP GOES HERE
        if (res == -1){ 
            // failed to find valid combination of coins
        } else {
            if( minCost < res + x ){
                // do nothing
            } else { // update minimum
                minCost = res + x;
                best_coin = coins[idx];
            }
        }
    }
    <<<<<< PUSH BEST COIN
return (minCost == Integer.MAX_VALUE) ? -1 : minCost;
...