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

``````

Considering a method with the following signature:

``````public static List<List<String>> getListOfBuyableItems(
``````

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

double amount = budget;

}
}
}

if (budget > 0.00) {
}
}
}
``````

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<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 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
}
else
{
// Search for an item that fits in the budget
{
if(item.price<=budget)
{
solve(items, i, budget-item.price);
items.remove(items.size()-1);
}
}
}
}

public static void main(String[] args)
{

``````Solution 1: [Fruit, Salad]