3

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

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

public interface Exchanging {
    Map<Integer, Integer> 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<Integer, Integer> exchange() {
        Map<Integer, Integer> 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;
        }
    }
}
0

3 ответа 3

4

Решение, представленное на Хабре, заключается в том, что количество вариантов набора текущей суммы - это сумма количества вариантов набора меньших сумм, из которых можно получить текущую сумму "докидыванием" одной монеты. Причем номинал монеты должен быть не меньше номиналов монет, входящих в варианты меньших сумм, дабы, например, вариант 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<Way> 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 для работы с полученными списками монет.


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

  1. WaysGroup создаются только при необходимости и удаляются сразу же, как только перестают быть нужными. Это сильно уменьшает затраты памяти и ускоряет работу примерно вдвое.
  2. В Way используется Integer[] вместо ArrayList<Integer>. Благодаря более быстрой обработке public void add(int coin) это ускоряет работу при больших значениях в несколько раз.
7
  • А не вы не могли бы добавить комментарии к коду очень хочется понять но вот уже больше часа сижу((( и не как((( буду очень признателен
    – Pavel
    18 янв 2017 в 15:54
  • хотя бы в целом за что отвечают Way и WaysGroup и сам алгоритм у меня там просто глаза в кучу и все(((
    – Pavel
    18 янв 2017 в 15:56
  • 1
    @Павел описание самого алгоритма я добавил в начало ответа. Для чего нужны Way и WaysGroup указано перед их кодом. Что конкретно непонятно?
    – Regent
    18 янв 2017 в 15:58
  • 1
    @Павел размен - это набор монет. Этот набор (а точнее номиналы монет) хранится в виде Integer[] в Way. В WaysGroup хранится список вариантов размена. В алгоритме он используется для хранения вариантов размена для Х суммы с использованием монет от первой до У. А ещё он используется для выдачи из метода всех требуемых вариантов размена.
    – Regent
    18 янв 2017 в 15:59
  • пардон мне надо было страницу обновить а я все на старый вариант смотрю...
    – Pavel
    18 янв 2017 в 16:02
2

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

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

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

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

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

    //из лямбды нельзя рекурсивно ссылаться на себя же :(
    class Wrapper<T> {
        private T function;
    }
    Wrapper<Function<Integer, BiConsumer<Integer, List<Integer>>>> 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

7
  • Интересно: кто меньше чем за минуту смог оценить решение, дабы кинуть минус?
    – Regent
    18 янв 2017 в 13:19
  • @Regent Дружище, без понятия)))
    – Artem
    18 янв 2017 в 13:20
  • @Regent круто 0_o А не могли бы в двух словах пояснить в чем идея алгоритма?
    – Pavel
    18 янв 2017 в 14:53
  • @Павел вас интересует мой вариант или вариант Artem Konovalov?
    – Regent
    18 янв 2017 в 14:56
  • ваш, просто я только что прошел тему дженериков и осталось ощющение что я их и понимаю и не понимаю, а у вас как раз вариант с дженериками я подумал если пойму вашу идею то и с дженериками закончку)))
    – Pavel
    18 янв 2017 в 15:13
2

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

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<List<Integer>> exchange(int note) {
        return exchange(note, this.values[this.values.length - 1]);
    }

    private List<List<Integer>> exchange(int note, int maxCoin) {
        List<List<Integer>> 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<Integer> remain : exchange(note - coin, coin)) {
                    List<Integer> set = new ArrayList<>();
                    set.add(coin);
                    set.addAll(remain);
                    result.add(set);
                }
            }
        }
        return result;
    }

}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.