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

Question

Using Java 8, I am trying to figure out an algorithm / proper solution to see how to store a List<String> with buyable items within a certain allocated budget.

Suppose, a Map<String, Double> which contains the following keys / values:

Map<String, Double> menu = new HashMap<>();

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

---

Considering a method with the following signature:

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

The following rules need to be enforced:

• Budget = 4.30, then the ArrayList returned is:

  [["Fruit", "Fruit"]]
  

• Budget = 5.50, then the ArrayList returned is:

  [["Fries", "Fries"], ["Fruit", "Salad"]]
  

• Budget = 2.15, then the ArrayList returned is:

  [["Fruit"]]
  

---

This is what I've come up with, but I can't seem to figure out how to fix this using recursion and / or a different approach:

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 a different solution?

I'm just curious on now to solve this using either:

• Using for or while loops
• Java 8 features: Streams & Lambda

Answer 1

Here is a solution that uses recursion.

To make things easier, I have defined an Item class that stores the name and the price of an item. The price is expressed in cents to avoid rounding issues. The menu is a list of items.

import java.util.*;

public class Solver
{
    private ArrayList<Item> menu;
    private ArrayList<String[]> solutions;

    public static class Item
    {
        public String name;
        public int price;

        public Item(String name, int price)
        {
            this.name = name;
            this.price = price;
        }
    }

    public Solver(ArrayList<Item> menu)
    {
        this.menu = menu;
    }

    public ArrayList<String[]> solve(int budget)
    {
        solutions = new ArrayList<String[]>();
        solve(new ArrayList<Item>(), 0, budget);
        return solutions;
    }

    private void solve(ArrayList<Item> items, int first, int budget)
    {
        if(budget==0)
        {
            // We have found a solution, store it
            solutions.add(items.stream().map(e -> e.name).toArray(String[]::new));
        }
        else
        {
            // Search for an item that fits in the budget
            for(int i=first;i<menu.size();i++)
            {
                Item item = menu.get(i);
                if(item.price<=budget)
                {
                    items.add(item);
                    solve(items, i, budget-item.price);
                    items.remove(items.size()-1);
                }
            }
        }
    }

    public static void main(String[] args)
    {
        ArrayList<Item> menu = new ArrayList<Item>();
        menu.add(new Item("Fruit", 215));
        menu.add(new Item("Fries", 275));
        menu.add(new Item("Salad", 335));
        menu.add(new Item("Wings", 355));
        menu.add(new Item("Mozzarella", 420));
        menu.add(new Item("Plate", 580));

        Solver solver = new Solver(menu);
        ArrayList<String[]> solutions = solver.solve(550);
        for(int i=0;i<solutions.size();i++)
            System.out.println("Solution "+(i+1)+": "+Arrays.toString(solutions.get(i)));
    }
}

Output:

Solution 1: [Fruit, Salad]
Solution 2: [Fries, Fries]

Answer 2

This problem is a direct application of the Coin Change problem.

A dynamic programming solution can be constructed recursively as follows:

For each item, the solution is the combination of two cases:

1. The item is included in the solution
2. The item is excluded

For the first case, the solution is the results of getBuyableItems(Menu, budget - item.value) While for the second case the solution is getBuyableItems(Menu after removing {item}, budget).

public class Menu {
  List<Pair<String, Integer>> menu = new ArrayList<>();

  public Menu() {
    menu.add(Pair.of("Fruit", 215));
    menu.add(Pair.of("Fries", 275));
    menu.add(Pair.of("Salad", 335));
    menu.add(Pair.of("Wings", 355));
    menu.add(Pair.of("Mozzarella", 420));
    menu.add(Pair.of("Plate", 580));
  }

  public List<List<String>> getListOfBuyableItemsRec(int m, int budget) {
    if (budget == 0) {
      List<List<String>> list = new ArrayList<>();
      list.add(new ArrayList<>());
      return list;
    }
    if (budget < 0)
      return null;
    if (m <= 0 && budget > 0)
      return null;

    List<List<String>> exclude_m = getListOfBuyableItemsRec(m - 1, budget);

    List<List<String>> include_m = getListOfBuyableItemsRec(m, budget - menu.get(m - 1).getValue());

    if (include_m != null) {
      include_m = include_m.stream().map(l -> {
        l.add(menu.get(m - 1).getKey());
        return l;
      }).collect(Collectors.toList());
    } else
      include_m = new ArrayList<>();

    if (exclude_m != null)
      include_m.addAll(exclude_m);

    return include_m;
  }

  public static void main(String[] str) {
    Menu menu1 = new Menu();
    var res = menu1.getListOfBuyableItemsRec(6, 550);
    if (res != null && !res.isEmpty())
      res.stream().forEach(l -> System.out.println(l));
    else
      System.out.println("no solution has been found");
  }
}

Solutions 
[Fruit, Salad]
[Fries, Fries]

However, this solution is not efficient and it may cause a memory issue for large cases. There is another solution that uses a technique called memoization.

For this problem, we can define a table of all possible sub-problems and construct that table gradually until we reach the solution at the final position. Each cell in the table represents a case starting from 0 to the requested budget. Eventually, each cell will hold the solutions for the corresponding sub-problem. For example, table[215] will have one list {"Fruit"}. The advantage of this solution is that we don't need to compute the same sub-problem every time we need it.

A solution for table[j] can be constructed through item i (given j >= i) by grabbing all the solutions in table[j-i] and adding the item i key to those solutions.

public class Menu {
  //initialization code
  public List<List<String>> getListOfBuyableItemsIter(int m, int budget) {
    // table[i] will be storing the solutions for
    // value i. We need budget+1 rows as the table is constructed
    // in bottom up manner using the base case (budget = 0)
    List<List<String>>[] table = new List[budget + 1];

    for (int i = 0; i <= budget; i++)
      table[i] = new ArrayList<>();

    table[0].add(new ArrayList<>());

    // Pick all items one by one and update the table[] values after
    // the index greater than or equal to the value of the picked item
    IntStream.range(0, m).forEach(i -> {
      IntStream.rangeClosed(menu.get(i).getValue(), budget).forEach(j -> {
        List<List<String>> lists = table[j - menu.get(i).getValue()];
        List<List<String>> cloneLists = new ArrayList<>();
        for (var l : lists) {
          List<String> newList = new ArrayList<>(l);
          newList.add(menu.get(i).getKey());
          cloneLists.add(newList);
        }
        table[j].addAll(cloneLists);
      });
    });
    return table[budget];
  }

  public static void main(String[] str) {
    Menu menu1 = new Menu();
    //var res1 = menu1.getListOfBuyableItemsRec(6, 550);
    var res2 = menu1.getListOfBuyableItemsIter(6, 550);
    if (res2 != null && !res2.isEmpty())
      res2.stream().forEach(l -> System.out.println(l));
    else
      System.out.println("no solution has been found");
  }
}

Solutions:
[Fries, Fries]
[Fruit, Salad]

Answer 3

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

1. Prepare a stream of maps.

   1. Calculate how many times the minimum amount from the map fits in the budget, this is the number of IntStream iterations.

   2. Prepare a stub of the map of combinations: key - String[] the array of menu items, value - Integer the order amount, ¢ cents.

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

2. Reduce a stream of maps into one map.

   1. Sequentially summarize pairs of maps into one map, adding cheaper menu items to more expensive ones, i.e. sequentially summarize pairs of entries of two maps.

   2. Use the sorted arrays String[] and TreeMap with the comparator Arrays::compare to get rid of duplicates, i.e. permuted arrays.

   3. Use Integer amounts in cents instead of fractions Double to avoid inaccuracies when adding the amounts, e.g. 7.949999999999999 or 7.550000000000001.

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

3. Custom filters and representation of the resulting map as a list of strings.

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

Try it online!

class MenuCombinations {
    // the combinations of menu items that fit within the budget
    private Map<String[], Integer> combinations = Collections.emptyMap();

    /**
     * @param menu    the map of menu items
     * @param aBudget the allocated budget, double
     */
    public MenuCombinations(Map<String, Double> menu, double aBudget) {
        // incorrect incoming data
        if (menu == null || menu.size() == 0 || aBudget <= 0) return;
        // the allocated budget, ¢ cents
        int budget = (int) (aBudget * 100);
        // the cheapest menu item, ¢ cents
        int min = menu.values().stream()
            .mapToInt(val -> (int) (val * 100)).min().orElse(0);
        // incorrect incoming data
        if (min <= 0) return;
        // the stub of the map of combinations
        Map<String[], Integer> map = menu.entrySet().stream()
            .collect(Collectors.toMap(
                // key - the array of menu items
                e -> new String[]{e.getKey()},
                // value - the order amount, ¢ cents
                e -> (int) (e.getValue() * 100)));
        // the map of combinations
        this.combinations = IntStream.rangeClosed(0, budget / min)
            // Stream<Map<String[],Integer>>
            .mapToObj(i -> map)
            // appending cheaper menu items to more expensive ones
            .reduce((map1, map2) -> map1.entrySet().stream()
                .flatMap(entry1 -> {
                    // sum of the chosen menu items
                    int sum = entry1.getValue();
                    // if the allocated budget is exceeded
                    if (sum > budget) return Stream.empty();
                    // if the allocated budget is reached
                    if (sum + min > budget)
                        return Stream.of(Map.ofEntries(entry1));
                    // otherwise, continue appending menu items
                    return map2.entrySet().stream()
                        // skip those items that are greater
                        .filter(entry2 -> entry2.getValue() + sum <= budget)
                        // summing two map entries, appending the previous one
                        .map(entry2 -> Map.of(
                            // new key - the sorted array of menu items
                            Stream.of(entry1, entry2)
                                .map(Map.Entry::getKey)
                                .flatMap(Arrays::stream)
                                .sorted() // for comparison
                                .toArray(String[]::new),
                            // new value - the order amount, ¢ cents
                            entry1.getValue() + entry2.getValue(),
                            // add the previous combination to the new one
                            entry1.getKey(), entry1.getValue()));
                }) // map without duplicates, i.e. permuted arrays
                .collect(() -> new TreeMap<>(Arrays::compare),
                    TreeMap::putAll, TreeMap::putAll))
            // otherwise, an empty map
            .orElse(Collections.emptyMap());
    }

    /**
     * @param min the minimum number of items in the order, inclusive
     * @param max the maximum number of items in the order, inclusive
     * @return the representation of filtered combinations
     */
    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 the items that should be present
     * @return the representation of filtered combinations
     */
    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 the lower bound of the order amount, inclusive
     * @return the representation of filtered combinations
     */
    public List<String> minAmount(double min) {
        return combinations.entrySet().stream()
            .filter(entry -> entry.getValue() >= (int) (min * 100))
            .map(MenuCombinations::entryToString)
            .collect(Collectors.toList());
    }

    /**
     * @return the string representation of the combinations map
     */
    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(", ", "[", "]"));
    }

    // supplementary method, returns formatted string
    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("Map of combinations for a budget of: 8.50");
    new MenuCombinations(menu, 8.5).get().forEach(System.out::println);
}

Output:

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

Map of combinations for a budget of: 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

---

^{See also: Integer partition iterative code optimization}

Answer 4

In a very very very inefficient way - I think it is something like O(n2^(nm)) - you can do it as follows;

The actual problem reminds an extended version of one dimension Knapsack Algorithm, and I really doubt if it can be done in a better complexity without using heuristic algorithms... This may be a good question for https://cs.stackexchange.com/help/on-topic

void budget() throws Exception {
    Map<String, Double> menu = new HashMap<>();

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

    System.out.println(new ObjectMapper().writeValueAsString(calcBudget(menu, 5)));
}

List<List<String>> calcBudget(Map<String, Double> menu, double budget) {
    List<List<String>> ret = new ArrayList<>();
    List<String> menuReplicated = new ArrayList<>();
    for (String s : menu.keySet()) {
        menuReplicated.addAll(Collections.nCopies((int) (budget / menu.get(s).doubleValue()), s));
    }
    String[] menuItems = menuReplicated.toArray(new String[]{});
    for (int i = 1; i < Math.pow(2, menuItems.length); i++) {
        List<String> items = new ArrayList<>();
        double total = 0;
        for (int j = 0; j < menuItems.length; j++) {
            if (((int) Math.pow(2, (j)) | i) == i) {
                total += menu.get(menuItems[j]).doubleValue();
                if (total <= budget) {
                    items.add(menuItems[j]);
                }
            }
        }
        if (items.size() > 0) {
            if (!ret.contains(items))
                ret.add(items);
        }
    }
    return ret;
}

The output is

[["Wings"],["Fruit"],["Fruit","Fruit"],["Fries"],["Fruit","Fries"],["Mozzarella"],["Salad"]]

Answer 5

As pointed out in other solutions, it might be better to store the prices in cents to avoid rounding errors.

Also, since there's no need for getting a value through a key, you could create a new class to store the Item/Price pairs or use the Pair class using import javafx.util.Pair to achieve the same behavior. Your new menu data structure should look like this if you decide to use Pair:

List<Pair<String,Integer>> menu = new ArrayList<>();
menu.add(new Pair<>("Fruit", 215));
menu.add(new Pair<>("Fries", 275));
menu.add(new Pair<>("Salad", 335));
menu.add(new Pair<>("Wings", 355));
menu.add(new Pair<>("Mozzarella", 420));
menu.add(new Pair<>("Plate", 580));

This is a recursive solution that works by subtracting the price of every item recursively from the budget and putting them on a builder list until the budget reaches 0. If it reaches exactly 0, you add it to the list. If it reaches a negative number, you skip it.

To avoid redundancy, you provide an index to check all items starting from that index. This will prevent the algorithm from adding both [Fruit, Salad] and [Salad, Fruit] which are the same but in different order.

public static List<List<String>> getListOfBuyableItems(
        List<Pair<String, Integer>> menu, double budget) {
    List<List<String>> buyableItems = new ArrayList<>();
    if (budget != 0 && menu.size() != 0)
        keepBuying(menu, budget, new ArrayList<>(), buyableItems, 0);
    return buyableItems;
}

public static void keepBuying(
        List<Pair<String, Integer>> menu,
        double budget,
        ArrayList<String> itemBuilder,
        List<List<String>> buyableItems,
        int index) {
    for (int i = index; i < menu.size(); i++) {
        Pair<String, Integer> item = menu.get(i);
        itemBuilder.add(item.getKey());
        int price = item.getValue();
        if (budget - price == 0)
            buyableItems.add(new ArrayList<>(itemBuilder));
        else if (budget - price > 0)
            keepBuying(menu, budget - price, itemBuilder, buyableItems, i);
        itemBuilder.remove(item.getKey());
    }
}

If your budget is ridiculously high or you're going to run this method a lot of times, you might want to consider a dynamic programming approach.

Answer 6

Solution of the above problem in Swift 5 :)

func getListOfBuyableItems(_ menu: [String: Double], _ budget: Double) -> [[String]] {
    var allList = [[String]]()
    var list = [String]()
    let menu = menu.map{ (item: $0.key, cost: $0.value) }
    getList(menu, 0, budget, &list, &allList)
    return allList
}

func getList(_ menu: [(item: String, cost: Double)],_ start: Int, _ budget: Double, _ list: inout [String], _ allList: inout [[String]])  {
    
    if budget == 0 {
        allList.append(list)
    } else {
        for index in start...menu.count-1 {
            let item = menu[index]
            if budget >= item.cost {
                list.append(item.item)
                getList(menu, index, budget - item.cost, &list, &allList)
                list.removeLast()
            }
        }
    }
}

var menu = ["Fruit": 2.15,
            "Fries": 2.75,
            "Salad": 3.35,
            "Wings": 3.55,
            "Mozzarella": 4.20,
            "Plate": 5.80]

getListOfBuyableItems(menu, 4.30) // [["Fruit", "Fruit"]]
getListOfBuyableItems(menu, 5.50) // [["Fruit", "Salad"], ["Fries", "Fries"]]
getListOfBuyableItems(menu, 2.15) // [["Fruit"]]