Algorithm or solution for selecting possible combinations of menu items within a budget
Solution 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]
Solution 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:
- The item is included in the solution
- 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]