javaalgorithmcombinationsmultisetcoin-change

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


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

Solution

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