java – Algorithm or solution for selecting possible combinations of menu items within a budget

Question:

I am using Java 8 . I'm trying to find an algorithm/suitable solution to figure out how to store a List<String> with purchasable items within a certain allocated budget.

Let's say there is a map Map<String, Double> which contains the following keys/values:

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);

Consider a method with the following signature:

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

The following rules must be observed:

  • Budget = 4.30, then the returned ArrayList contains: [["Fruit", "Fruit"]]
  • Budget = 5.50, then the returned ArrayList contains: [["Fries", "Fries"], ["Fruit", "Salad"]]
  • Budget = 2.15 then the returned ArrayList contains: [["Fruit"]]

Here's what I came up with but can't figure out yet how to fix it using recursion and/or another solution:

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();
        }
    }
}

How can I solve this problem using recursion or some other approach?

What are the options using:

  • for or while loops .
  • Java 8 features : Stream & Lambda.

Translation of the Algorithm or solution for selecting possible combinations of menu items within a budget question by @PacificNW_Lover .

Answer:

The multiset in this case consists of several combinations of menu items that fit into a certain budget. Menu items can be repeated, and permutations of combinations are considered the same, for example [a,a,b,c] and [c,a,b,a] are the same. Such a multiset can be implemented and stored using a Map<String[],Integer> with additional filtering methods to represent it as a List<String> .

  1. Map preparing a stream of maps Stream<Map> .

    1. Let's count how many times the minimum amount from the map fits into the budget, this will be the number of iterations of IntStream .

    2. Let's prepare a combination map: key – String[] array of menu items, value – Integer order amount, in kopecks.

    3. We get a stream of maps Stream<Map<String[],Integer>> .

  2. Reduce we reduce the flow of cards into one card.

    1. Sequentially sum pairs of maps into one map, adding cheaper menu items to more expensive ones, i.e., sequentially summing the entries of two maps Map.Entry .

    2. We will use sorted String[] and TreeMap arrays with the Arrays::compare comparator to eliminate duplicates, i.e. permutations of combinations.

    3. We use integer sums in kopecks Integer instead of fractional Double , to avoid inaccuracies when adding sums, for example 7.949999999999999 or 7.550000000000001 .

    4. We get a map of combinations Map<String[],Integer> .

  3. Methods for filtering and presenting the resulting map as a List<String> .

    1. quantity(min,max) by the number of menu items in the order.
    2. contains(items) on the presence of certain menu items.
    3. minAmount(min) on the lower limit of the order amount.
    4. get() string representation of the combination map.

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);
}

Conclusion:

[[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

Post Views: 2
Scroll to Top