5

Использую Java 8. Пытаюсь найти алгоритм / подходящее решение, чтобы понять, как хранить List<String> с покупабельными товарами в рамках определенного выделенного бюджета.

Допустим, есть карта Map<String, Double> которая содержит следующие ключи / значения:

menu.put("Fruit", 2.15);
menu.put("Fries", 2.75);
menu.put("Salad", 3.35);
menu.put("Wings", 3.55);
menu.put("Mozzarella", 4.20);
menu.put("Plate", 5.80);

Рассмотрим метод со следующей сигнатурой:

public static List<List<String>> getListOfBuyableItems(
        Map<String, Double> menu, double budget)

Следующие правила должны быть соблюдены:

  • Бюджет = 4.30, тогда возвращаемый ArrayList содержит: [["Fruit", "Fruit"]]
  • Бюджет = 5.50, тогда возвращаемый ArrayList содержит: [["Fries", "Fries"], ["Fruit", "Salad"]]
  • Бюджет = 2.15, тогда возвращаемый ArrayList содержит: [["Fruit"]]

Вот что я придумал, но пока не могу сообразить, как это исправить, используя рекурсию и / или другое решение:

public static List<List<String>> getBuyableItems(
        Map<String, Double> menu, double budget) {
    if (menu.isEmpty() || budget < 1) {
        return Collections.emptyList();
    }

    List<List<String>> buyableItems = new ArrayList<>();
    double amount = budget;

    for (Map.Entry<String, Double> menuItem : menu.entrySet()) {
        System.out.println(menuItem.getKey() + " $" + menuItem.getValue());
        if (budget > menuItem.getValue()) {
            buyableItems.add(menuItem.getKey());
            keepBuying(menu, budget);
            amount = budget - menuItem.getValue();
        }
    }
    return buyableItems;
}

public static void keepBuying(Map<String, Double> menu, double budget) {
    if (budget > 0.00) {
        for (Map.Entry<String, Double> menuItem : menu.entrySet()) {
            budget -= menuItem.getValue();
        }
    }
}

Как мне решить эту задачу при помощи рекурсии или другого подхода?

Какие могут быть варианты с использованием:

  • Циклов for или while.
  • Возможностей Java 8: Stream & Lambda.

Перевод вопроса Algorithm or solution for selecting possible combinations of menu items within a budget от участника @PacificNW_Lover.

4
  • ассоциация:stackoverflow.com/q/68606334/2881286
    – Grundy
    14 авг 2021 в 17:45
  • @DuncanMacLeod, при переводах нужно добавлять источник и для ответа и для вопроса.
    – Grundy
    14 авг 2021 в 17:46
  • Такие правила
    – Grundy
    14 авг 2021 в 19:47
  • Не нужно откатывать правки, приводящие вопрос в соответствие правилам.
    – Grundy
    14 авг 2021 в 20:11

1 ответ 1

6

Мультимножество в данном случае состоит из нескольких комбинаций пунктов меню, которые вписываются в определенный бюджет. Пункты меню могут повторяться, а перестановки комбинаций считаются одинаковыми, например [a,a,b,c] и [c,a,b,a] одинаковые. Такое мультимножество можно реализовать и сохранить с использованием Map<String[],Integer> с дополнительными методами фильтрации для представления его в виде List<String>.

  1. Map подготовка потока карт Stream<Map>.

    1. Подсчитаем, сколько раз минимальная сумма из карты вписывается в бюджет, это будет количество итераций IntStream.

    2. Подготовим карту комбинаций: key - String[] массив пунктов меню, value - Integer сумма заказа, в копейках.

    3. Получаем поток карт Stream<Map<String[],Integer>>.

  2. Reduce сводим поток карт в одну карту.

    1. Последовательно суммируем пары карт в одну карту, добавляя более дешевые пункты меню к более дорогим, т. е. последовательно суммируем записи двух карт Map.Entry.

    2. Будем использовать отсортированные массивы String[] и TreeMap с компаратором Arrays::compare, чтобы исключить дубликаты, т. е. перестановки комбинаций.

    3. Используем целочисленные суммы в копейках Integer вместо дробных Double, чтобы исключить неточности при сложении сумм, например 7.949999999999999 или 7.550000000000001.

    4. Получаем карту комбинаций Map<String[],Integer>.

  3. Методы фильтрации и представления результирующей карты в виде List<String>.

    1. quantity(min,max) по количеству пунктов меню в заказе.
    2. contains(items) по присутствию определенных элементов меню.
    3. minAmount(min) по нижней границе суммы заказа.
    4. get() строковое представление карты комбинаций.

Try it online!

class MenuCombinations {
    // комбинации пунктов меню, которые вписывается в выделенный бюджет
    private Map<String[], Integer> combinations = Collections.emptyMap();

    /**
     * @param menu    карта пунктов меню
     * @param aBudget выделенный бюджет, double
     */
    public MenuCombinations(Map<String, Double> menu, double aBudget) {
        // некорректные входящие данные
        if (menu == null || menu.size() == 0 || aBudget <= 0) return;
        // выделенный бюджет, в копейках
        int budget = (int) (aBudget * 100);
        // самый дешевый ункт меню, в копейках
        int min = menu.values().stream()
            .mapToInt(val -> (int) (val * 100)).min().orElse(0);
        // некорректные входящие данные
        if (min <= 0) return;
        // заготовка карты комбинаций
        Map<String[], Integer> map = menu.entrySet().stream()
            .collect(Collectors.toMap(
                // ключ - массив пунктов меню
                e -> new String[]{e.getKey()},
                // значение - сумма заказа, в копейках
                e -> (int) (e.getValue() * 100)));
        // карта комбинаций
        this.combinations = IntStream.rangeClosed(0, budget / min)
            // Stream<Map<String[],Integer>>
            .mapToObj(i -> map)
            // добавляем более дешевые пункты меню к более дорогим
            .reduce((map1, map2) -> map1.entrySet().stream()
                .flatMap(entry1 -> {
                    // сумма выбранных пунктов меню
                    int sum = entry1.getValue();
                    // если выделенный бюджет превышен
                    if (sum > budget) return Stream.empty();
                    // если выделенный бюджет достигнут
                    if (sum + min > budget)
                        return Stream.of(Map.ofEntries(entry1));
                    // иначе продолжаем добавлять пункты меню
                    return map2.entrySet().stream()
                        // пропускаем пункты меню, которые больше
                        .filter(entry2 -> entry2.getValue() + sum <= budget)
                        // суммируем записи двух карт, и добавляем предыдущую
                        .map(entry2 -> Map.of(
                            // новый ключ - отсортированный массив пунктов меню
                            Stream.of(entry1, entry2)
                                .map(Map.Entry::getKey)
                                .flatMap(Arrays::stream)
                                .sorted() // для компаратора
                                .toArray(String[]::new),
                            // новое значение - сумма заказа, в копейках
                            entry1.getValue() + entry2.getValue(),
                            // добавляем предыдущую комбинацию к новой
                            entry1.getKey(), entry1.getValue()));
                }) // карта без дубликатов, т. е. без перестановок
                .collect(() -> new TreeMap<>(Arrays::compare),
                    TreeMap::putAll, TreeMap::putAll))
            // иначе пустая карта
            .orElse(Collections.emptyMap());
    }

    /**
     * @param min минимальное количество пунктов меню в заказе, включительно
     * @param max максимальное количество пунктов меню в заказе, включительно
     * @return представление отобранных комбинаций
     */
    public List<String> quantity(int min, int max) {
        return combinations.entrySet().stream()
            .filter(entry -> entry.getKey().length >= min
                && entry.getKey().length <= max)
            .map(MenuCombinations::entryToString)
            .collect(Collectors.toList());
    }

    /**
     * @param items пункты меню, которые должны присутствовать
     * @return представление отобранных комбинаций
     */
    public List<String> contains(Set<String> items) {
        return combinations.entrySet().stream()
            .filter(entry -> Arrays.asList(entry.getKey())
                .containsAll(items))
            .map(MenuCombinations::entryToString)
            .collect(Collectors.toList());
    }

    /**
     * @param min нижняя граница суммы заказа, включительно
     * @return представление отобранных комбинаций
     */
    public List<String> minAmount(double min) {
        return combinations.entrySet().stream()
            .filter(entry -> entry.getValue() >= (int) (min * 100))
            .map(MenuCombinations::entryToString)
            .collect(Collectors.toList());
    }

    /**
     * @return строковое представление карты комбинаций.
     */
    public List<String> get() {
        return combinations.entrySet().stream()
            .map(MenuCombinations::entryToString)
            .collect(Collectors.toList());
    }

    @Override
    public String toString() {
        return combinations.entrySet().stream()
            .map(MenuCombinations::entryToString)
            .collect(Collectors.joining(", ", "[", "]"));
    }

    // вспомогательный метод, возвращает отформатированную строку
    private static String entryToString(Map.Entry<String[], Integer> e) {
        return String.format("%s=%d.%s", Arrays.toString(e.getKey()),
            e.getValue() / 100, (e.getValue() % 100 + "00").substring(0, 2));
    }
}
public static void main(String[] args) {
    Map<String, Double> menu = Map.of(
            "Fruit", 2.15, "Fries", 2.75, "Salad", 3.35,
            "Wings", 3.55, "Mozzarella", 4.20, "Plate", 5.80);

    System.out.println(new MenuCombinations(menu, 4.30).quantity(2, 2));
    System.out.println(new MenuCombinations(menu, 5.5).minAmount(5.5));
    System.out.println(new MenuCombinations(menu, 2.15));
    System.out.println(new MenuCombinations(menu, 8.60).quantity(4, 4));
    System.out.println(new MenuCombinations(menu, 9.2).contains(Set.of("Plate")));

    System.out.println("Карта комбинаций для бюджета: 8.50");
    new MenuCombinations(menu, 8.5).get().forEach(System.out::println);
}

Вывод:

[[Fruit, Fruit]=4.30]
[[Fries, Fries]=5.50, [Fruit, Salad]=5.50]
[[Fruit]=2.15]
[[Fruit, Fruit, Fruit, Fruit]=8.60]
[[Fries, Plate]=8.55, [Fruit, Plate]=7.95, [Plate]=5.80, [Plate, Salad]=9.15]
Карта комбинаций для бюджета: 8.50
[Fries]=2.75
[Fries, Fries]=5.50
[Fries, Fries, Fries]=8.25
[Fries, Fries, Fruit]=7.65
[Fries, Fruit]=4.90
[Fries, Fruit, Fruit]=7.50
[Fries, Fruit, Salad]=8.25
[Fries, Fruit, Wings]=8.45
[Fries, Mozzarella]=6.95
[Fries, Salad]=6.10
[Fries, Wings]=6.30
[Fruit]=2.15
[Fruit, Fruit]=4.30
[Fruit, Fruit, Fruit]=6.45
[Fruit, Fruit, Mozzarella]=8.50
[Fruit, Fruit, Salad]=7.65
[Fruit, Fruit, Wings]=7.85
[Fruit, Mozzarella]=6.35
[Fruit, Plate]=7.95
[Fruit, Salad]=5.50
[Fruit, Wings]=5.70
[Mozzarella]=4.20
[Mozzarella, Mozzarella]=8.40
[Mozzarella, Salad]=7.55
[Mozzarella, Wings]=7.75
[Plate]=5.80
[Salad]=3.35
[Salad, Salad]=6.70
[Salad, Wings]=6.90
[Wings]=3.55
[Wings, Wings]=7.10

См. The map-and-reduce approach to build a multiset

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки