Перебор всех возможных вариантов размена суммы на маленькие монеты

#java #алгоритм

У меня было задание сделать программу, которая будет разменивать большую купюру на
мелкие монеты. Это у меня худо-бедно получилось. Теперь добавилось условие: чтобы возвращались
все возможные варианты размена. И тут я что-то поплыл.   

Как можно модифицировать код, чтобы получить не один вариант размена, а все?

public interface Exchanging {
    Map exchange();
}

public class Exchange implements Exchanging {
    /**
     * Money which should be exchanging.
     */
    private final int sumForExchange;
    /**
     * Nominal coins.
     */
    private final int[] denominationСoins;

    /**
     * Default constructor.
     *
     * @param sumForExchange    money which should be exchanging.
     * @param denominationСoins array with nominal coins.
     */
    public Exchange(final int sumForExchange, final int... denominationСoins) {
        this.denominationСoins = denominationСoins;
        this.sumForExchange = sumForExchange;
    }

    /**
     * Exchange big money on less coins.
     *
     * @return map with coins. Nominal is key, amount coin is value.
     */
    @Override
    public Map exchange() {
        Map result = new HashMap<>();
        int[] coins = sort();
        int residue = sumForExchange;

        for (int i = 0; i != coins.length; i++) {
            ExchangeByValue exchangeByValue = new ExchangeByValue(
                    residue, coins[i]);

            // how much coins content current residue for denominationСoins[i].
            int amountCoin = exchangeByValue.exchange();
            result.put(coins[i], amountCoin);
            // update residue.
            residue = exchangeByValue.getResidue();
        }
        return result;
    }

    /**
     * Sorting array with coins nominal.
     *
     * @return arr sort by descending.
     */
    private int[] sort() {
        int[] result = denominationСoins;
        for (int i = result.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (result[j] < result[j + 1]) {
                    int temp = result[j];
                    result[j] = result[j + 1];
                    result[j + 1] = temp;
                }
            }
        }
        return result;
    }

    /**
     * Calculate residue and amount coins.
     */
    private class ExchangeByValue {
        /**
         * Residue for division on coins.
         */
        private final int denomination;
        /**
         * Nominal coin.
         */
        private final int divider;

        /**
         * Default constructor.
         *
         * @param denomination Residue for division on coins.
         * @param divider      Nominal coin.
         */
        private ExchangeByValue(final int denomination, final int divider) {
            this.denomination = denomination;
            this.divider = divider;
        }

        /**
         * @return amount coins which may by get for this.denomination.
         */
        private int exchange() {
            return denomination / divider;
        }

        /**
         * @return residue for future exchange.
         */
        private int getResidue() {
            return denomination % divider;
        }
    }
}

    

Ответы

Ответ 1

А у меня получилось такое решение:

List coins = Arrays.asList(1, 2, 5);
coinsChange(10, coins).forEach(System.out::println);


реализация метода

public static List> coinsChange(int countOfMoney,
                                             List coins) {

    Collections.sort(coins);
    List> result = new ArrayList<>();

    //из лямбды нельзя рекурсивно ссылаться на себя же :(
    class Wrapper {
        private T function;
    }
    Wrapper>>> recursion = new
Wrapper<>();
    recursion.function = money -> (numberOfCoin, buffer) -> {
        if (money < 0 || numberOfCoin < 0)
            return;

        if (money == 0) {
            result.add(buffer);
            return;
        }

        recursion.function.apply(money).accept(numberOfCoin - 1, new ArrayList<>(buffer));
        int coin = coins.get(numberOfCoin);
        buffer = new ArrayList<>(buffer);
        buffer.add(coin);
        recursion.function.apply(money - coin).accept(numberOfCoin, buffer);
    };

    recursion.function.apply(countOfMoney).accept(coins.size() - 1, new ArrayList<>());

    return result;
}


UPD обновил решение, попытался переписать в функциональном стиле, насколько это позволила
мне сделать java


Ответ 2

Решение, представленное на Хабре, заключается в том, что количество вариантов набора
текущей суммы - это сумма количества вариантов набора меньших сумм, из которых можно
получить текущую сумму "докидыванием" одной монеты. Причем номинал монеты должен быть
не меньше номиналов монет, входящих в варианты меньших сумм, дабы, например, вариант
1 1 5 не учитывался ещё и как 1 5 1 и 5 1 1.

Сохранение всех вариантов ощутимо усложняет код. В итоге получается так:

Way.java для хранения конкретного варианта размена:

public class Way
{
    private final Integer[] coins;

    public Way()
    {
        coins = new Integer[0];
    }

    public Way(Way way)
    {
        coins = new Integer[way.coins.length + 1];
        System.arraycopy(way.coins, 0, coins, 0, way.coins.length);
    }

    public void add(int coin)
    {
        coins[coins.length - 1] = coin;
    }

    public void print()
    {
        for (int i = 0; i < coins.length - 1; i++)
        {
            System.out.print(coins[i] + " ");
        }
        System.out.println();
    }
}


WaysGroup.java для хранения групп вариантов размена:

import java.util.*;

public class WaysGroup
{
    private final List ways;

    public WaysGroup()
    {
        ways = new ArrayList<>();
    }

    public void add(Way way)
    {
        ways.add(way);
    }

    public void add(int coin)
    {
        for (Way way : ways)
        {
            way.add(coin);
        }
    }

    public void add(WaysGroup group)
    {
        if (group == null)
        {
            return;
        }
        for (Way way : group.ways)
        {
            ways.add(new Way(way));
        }
    }

    public void print()
    {
        for (Way way : ways)
        {
            way.print();
        }
    }
}


Сам алгоритм в Exchange.java:

public WaysGroup getAllExchanges()
{
    int[] coins = denominationСoins;
    WaysGroup[][] waysGroups = new WaysGroup[coins.length][sumForExchange + 1];
    waysGroups[0][0] = new WaysGroup();
    waysGroups[0][0].add(new Way());
    for (int i = 0; i < sumForExchange; i++)
    {
        for (int j = 0; j < coins.length; j++)
        {
            for (int k = j; k < coins.length; k++)
            {
                if (i + coins[k] <= sumForExchange)
                {
                    if (waysGroups[k][i + coins[k]] == null)
                    {
                        waysGroups[k][i + coins[k]] = new WaysGroup();
                    }
                    waysGroups[k][i + coins[k]].add(waysGroups[j][i]);
                }
            }
            if (i + coins[j] <= sumForExchange)
            {
                waysGroups[j][i + coins[j]].add(coins[j]);
            }
            waysGroups[j][i] = null;
        }
    }
    WaysGroup result = new WaysGroup();
    for (int i = 0; i < coins.length; i++)
    {
        result.add(waysGroups[i][sumForExchange]);
    }
    return result;
}


И, наконец, небольшой тест:

public static void main(String[] args)
{
    Exchange exchange = new Exchange(10, 1, 2, 3);
    WaysGroup allWays = exchange.getAllExchanges();
    allWays.print();
}


Код рассчитан на вывод значений на экран, однако вполне можно добавить getter-ы в
Way и WaysGroup для работы с полученными списками монет.



Проведённые оптимизации, которые, возможно, делают код менее понятным:


WaysGroup создаются только при необходимости и удаляются сразу же, как только перестают
быть нужными. Это сильно уменьшает затраты памяти и ускоряет работу примерно вдвое.
В Way используется Integer[] вместо ArrayList. Благодаря более быстрой обработке
public void add(int coin) это ускоряет работу при больших значениях в несколько раз.


Ответ 3

Еще один вариант:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CashMachine {

    private final int[] values;

    public CashMachine(final int[] values) {
        this.values = values;
        Arrays.sort(this.values);
    }

    public List> exchange(int note) {
        return exchange(note, this.values[this.values.length - 1]);
    }

    private List> exchange(int note, int maxCoin) {
        List> result = new ArrayList<>();
        if (note == 0) {
            result.add(new ArrayList<>());
        } else {
            for (int i = this.values.length - 1; i >= 0; i--) {
                int coin = values[i];
                if (coin > note || coin > maxCoin) {
                    continue;
                }
                for (List remain : exchange(note - coin, coin)) {
                    List set = new ArrayList<>();
                    set.add(coin);
                    set.addAll(remain);
                    result.add(set);
                }
            }
        }
        return result;
    }

}