在预算内选择可能的菜单项组合的算法或解决方案

PacificNW_Lover
2021-08-01  
1120  
    
6  

使用 Java 8 ，我试图找出一种算法/适当的解决方案，以查看如何在特定分配的预算内存储带有可购买物品的 List<String> 。

假设，一个 Map<String, Double> 包含以下键/值：

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

考虑具有以下签名的方法：

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

需要执行以下规则：

  • 预算 = 4.30，则返回的 ArrayList 为： ```
    [["Fruit", "Fruit"]]

  • 预算 = 5.50，则返回的 ArrayList 为： ```
    [["Fries", "Fries"], ["Fruit", "Salad"]]

  • Budget = 2.15，则返回的ArrayList为： ```
    [["Fruit"]]

    • *

这是我想出的，但我似乎无法弄清楚如何使用递归和/或不同的方法来解决这个问题：

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

如何使用递归或其他解决方案解决此问题？

我现在只是好奇使用以下方法解决这个问题：

  • 使用 for 或 while 循环
  • Java 8 功能：流和 Lambda
java ,  algorithm ,  combinations ,  multiset ,  coin-change
stack overflow Algorithm or solution for selecting possible combinations of menu items within a budget
原文答案
author avatar
Olivier
2021-08-05
4
     原文

接受的答案

这是一个使用递归的解决方案。

为了使事情更容易，我定义了一个 Item 类来存储商品的名称和价格。价格以美分表示，以避免四舍五入问题。菜单是项目列表。

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

输出：

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

答案:

作者头像
AlHassan
2021-08-06    3      原文

这个问题是硬币找零问题的直接应用。

可以递归地构造动态规划解决方案，如下所示：

对于每个项目，解决方案是两种情况的组合：

1.该项目包含在解决方案中
2.该项目被排除在外

对于第一种情况，解决方案是 getBuyableItems(Menu, budget - item.value) 的结果，而对于第二种情况，解决方案是 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]

但是，此解决方案效率不高，并且可能会导致大型案例的内存问题。还有另一种解决方案使用了一种称为记忆的技术。

对于这个问题，我们可以定义一个包含所有可能子问题的表格，并逐步构建该表格，直到我们到达最终位置的解决方案。表中的每个单元格代表一个从 0 开始到请求预算的案例。最终，每个单元将保存相应子问题的解决方案。例如，table[215] 将有一个列表 {"Fruit"}。这种解决方案的优点是我们不需要每次需要时都计算相同的子问题。

通过获取 table[j-i] 中的所有解决方案并将项 i 键添加到这些解决方案，可以通过项 i（给定 j >= i）构造 table[j] 的解决方案。

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]
作者头像
user16596785
2021-08-05    1      原文

在这种情况下， multiset 由适合特定预算的菜单项的多个组合组成。菜单项可以重复，并且排列组合被认为是相同的，例如 [a,a,b,c] 和 [c,a,b,a] 是一样的。这样的 multiset 可以使用 Map<String[],Integer> 来实现和存储，并带有用于将其表示为 List<String> 的附加过滤方法。

  1. 准备一系列地图。

    1. 计算地图中的最小数量符合预算的次数，这是 IntStream 迭代的次数。

    2. 准备组合图的存根： key - String[] 菜单项数组， value - Integer 订单金额，¢ 美分。

    3. 获取地图流 Stream<Map<String[],Integer>> 。

  2. 将一系列地图缩减为一张地图。

    1. 将成对的地图顺序汇总到一张地图中，将更便宜的菜单项添加到更昂贵的菜单项中，即顺序汇总两个地图的条目对。

    2. 将排序数组 String[] 和 TreeMap 与比较器 Arrays::compare 一起使用以消除重复，即置换数组。

    3. 使用以美分为单位的 Integer 金额而不是分数 Double 以避免在添加金额时不准确，例如 7.949999999999999 或 7.550000000000001 。

    4. 获取组合图 Map<String[],Integer> 。

  3. 自定义过滤器和将结果映射表示为字符串列表。

    1. quantity(min,max) 按订单中的项目数。
    2. contains(items) 通过某些项目的存在。
    3. minAmount(min) 按订单金额的下限。
    4. get() 组合映射的字符串表示。

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

}


输出：

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



* * *

另见： [Integer partition iterative code optimization](https://stackoverflow.com/a/67340118/16596785)
作者头像
Kemal Kaplan
2021-08-01    0      原文

以一种非常非常低效的方式 - 我认为它类似于 O(n2^(nm)) - 你可以按如下方式进行；

实际问题让人想起一维背包算法的扩展版本，我真的怀疑它是否可以在不使用启发式算法的情况下以更好的复杂度完成......这对于 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;
}

输出是

[["Wings"],["Fruit"],["Fruit","Fruit"],["Fries"],["Fruit","Fries"],["Mozzarella"],["Salad"]]
作者头像
Eddy Todd
2021-08-10    0      原文

正如在其他解决方案中所指出的，最好以美分存储价格以避免舍入错误。

此外，由于不需要通过键获取值，您可以创建一个新类来存储商品/价格对或使用 Pair 类来实现相同的行为。如果您决定使用 import javafx.util.Pair ，您的新 menu 数据结构应该如下所示：

Pair

这是一个递归解决方案，它通过从预算中递归地减去每个项目的价格并将它们放在构建器列表中，直到预算达到 0。如果它恰好达到 0，则将其添加到列表中。如果它达到负数，则跳过它。

为避免冗余，您提供一个索引来检查从该索引开始的所有项目。这将防止算法同时添加相同但顺序不同的 ```
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));

`` 和[Fruit, Salad]` 。

[Salad, Fruit]

如果您的预算高得离谱，或者您要多次运行此方法，您可能需要考虑动态编程方法。

作者头像
osama
2022-01-22    0      原文

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

相关问题

标签