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]