用于在预算内选择可能的菜单项组合的算法或解决方案
Algorithm or solution for selecting possible combinations of menu items within a budget
使用 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)
需要执行以下规则：
- Budget = 4.30，则返回的ArrayList为：
[["Fruit", "Fruit"]]
- Budget = 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
以一种非常非常非常低效的方式 - 我认为它类似于 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"]]
这是一个使用递归的解决方案。
为了方便起见，我定义了一个 Item class 来存储商品的名称和价格。
价格以美分表示以避免四舍五入问题。菜单是项目列表。
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]
本例中的 multiset 由适合特定预算的菜单项的多个组合组成。菜单项可以重复，排列的组合被认为是相同的，例如[a,a,b,c] 和 [c,a,b,a] 是一样的。这样的 multiset 可以使用 Map<String[],Integer> 和额外的过滤方法来实现和存储，以将其表示为 List<String>.
准备地图流。
从地图中计算出多少次最小金额符合预算，这是IntStream次迭代的次数。
准备组合图的存根：key - String[]菜单项数组，value - Integer 订单金额，美分。
获取地图流Stream<Map<String[],Integer>>。
将一系列地图缩减为一张地图。
将成对的地图依次汇总为一张地图，将便宜的菜单项添加到昂贵的菜单项，即依次汇总两张地图的条目对。
使用排序数组 String[] 和 TreeMap 以及比较器 Arrays::compare 来去除重复项，即置换数组。
使用 Integer 金额而不是分数 Double 以避免添加金额时不准确，例如7.949999999999999 或 7.550000000000001.
获取组合图Map<String[],Integer>。
自定义过滤器并将生成的地图表示为字符串列表。
quantity(min,max) 按订单中的商品数量。contains(items) 某些项目的存在。minAmount(min)按订单金额下限get() 组合图的字符串表示。
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
这个问题是硬币找零问题的直接应用。
一个动态规划解可以递归构造如下：
对于每一项，解决方案是两种情况的组合：
- 项目包含在解决方案中
- 该项目已排除
对于第一种情况，解决方案是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]
但是，此解决方案效率不高，对于大型案例可能会导致内存问题。
还有另一种解决方案，它使用一种称为记忆的技术。
对于这个问题，我们可以定义一个table所有可能的子问题，并逐步构建table，直到我们到达最终位置的解决方案。
table 中的每个单元格代表一个从 0 开始到请求的预算的案例。最终，每个单元格将保存相应子问题的解决方案。
例如，table[215] 将有一个列表 {"Fruit"}。
这种解决方案的优点是我们不需要每次都计算相同的子问题。
table[j] 的解决方案可以通过第 i 项（给定 j >= i）构造，方法是抓取 table[j-i] 中的所有解决方案并将第 i 项键添加到这些解决方案。
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]
正如其他解决方案中所指出的，最好以美分存储价格以避免舍入误差。
此外，由于不需要通过键获取值，您可以创建一个新的 class 来存储 Item/Price 对或使用 Pair class 使用 import javafx.util.Pair 实现相同的行为。如果您决定使用 Pair:
，您的新 menu 数据结构应该如下所示
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));
这是一个递归解决方案，它的工作原理是从预算中递归地减去每件商品的价格，然后将它们放入制造商列表中，直到预算达到 0。如果恰好达到0，您将其添加到列表中。如果它达到负数，则跳过它。
为避免冗余，您提供了一个索引来检查从该索引开始的所有项目。这将防止算法添加相同但顺序不同的 [Fruit, Salad] 和 [Salad, Fruit]。
public static List<List<String>> getListOfBuyableItems(
List<Pair<String, Integer>> menu, double budget) {
List<List<String>> buyableItems = new ArrayList<>();
if (budget != 0 && menu.size() != 0)
keepBuying(menu, budget, new ArrayList<>(), buyableItems, 0);
return buyableItems;
}
public static void keepBuying(
List<Pair<String, Integer>> menu,
double budget,
ArrayList<String> itemBuilder,
List<List<String>> buyableItems,
int index) {
for (int i = index; i < menu.size(); i++) {
Pair<String, Integer> item = menu.get(i);
itemBuilder.add(item.getKey());
int price = item.getValue();
if (budget - price == 0)
buyableItems.add(new ArrayList<>(itemBuilder));
else if (budget - price > 0)
keepBuying(menu, budget - price, itemBuilder, buyableItems, i);
itemBuilder.remove(item.getKey());
}
}
如果您的预算高得离谱或者您要运行这种方法很多次，您可能需要考虑动态规划方法。
上述问题的解决方法在Swift5 :)
func getListOfBuyableItems(_ menu: [String: Double], _ budget: Double) -> [[String]] {
var allList = [[String]]()
var list = [String]()
let menu = menu.map{ (item: [=10=].key, cost: [=10=].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"]]
使用 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)
需要执行以下规则：
- Budget = 4.30，则返回的ArrayList为：
[["Fruit", "Fruit"]] - Budget = 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
以一种非常非常非常低效的方式 - 我认为它类似于 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"]]
这是一个使用递归的解决方案。
为了方便起见，我定义了一个 Item class 来存储商品的名称和价格。
价格以美分表示以避免四舍五入问题。菜单是项目列表。
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]
本例中的 multiset 由适合特定预算的菜单项的多个组合组成。菜单项可以重复，排列的组合被认为是相同的，例如[a,a,b,c] 和 [c,a,b,a] 是一样的。这样的 multiset 可以使用 Map<String[],Integer> 和额外的过滤方法来实现和存储，以将其表示为 List<String>.
准备地图流。
从地图中计算出多少次最小金额符合预算，这是
IntStream次迭代的次数。准备组合图的存根：key -
String[]菜单项数组，value -Integer订单金额，美分。获取地图流
Stream<Map<String[],Integer>>。
将一系列地图缩减为一张地图。
将成对的地图依次汇总为一张地图，将便宜的菜单项添加到昂贵的菜单项，即依次汇总两张地图的条目对。
使用排序数组
String[]和TreeMap以及比较器Arrays::compare来去除重复项，即置换数组。使用
Integer金额而不是分数Double以避免添加金额时不准确，例如7.949999999999999或7.550000000000001.获取组合图
Map<String[],Integer>。
自定义过滤器并将生成的地图表示为字符串列表。
quantity(min,max)按订单中的商品数量。contains(items)某些项目的存在。minAmount(min)按订单金额下限get()组合图的字符串表示。
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
这个问题是硬币找零问题的直接应用。
一个动态规划解可以递归构造如下：
对于每一项，解决方案是两种情况的组合：
- 项目包含在解决方案中
- 该项目已排除
对于第一种情况，解决方案是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]
但是，此解决方案效率不高，对于大型案例可能会导致内存问题。 还有另一种解决方案，它使用一种称为记忆的技术。
对于这个问题，我们可以定义一个table所有可能的子问题，并逐步构建table，直到我们到达最终位置的解决方案。 table 中的每个单元格代表一个从 0 开始到请求的预算的案例。最终，每个单元格将保存相应子问题的解决方案。 例如，table[215] 将有一个列表 {"Fruit"}。 这种解决方案的优点是我们不需要每次都计算相同的子问题。
table[j] 的解决方案可以通过第 i 项（给定 j >= i）构造，方法是抓取 table[j-i] 中的所有解决方案并将第 i 项键添加到这些解决方案。
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]
正如其他解决方案中所指出的，最好以美分存储价格以避免舍入误差。
此外，由于不需要通过键获取值，您可以创建一个新的 class 来存储 Item/Price 对或使用 Pair class 使用 import javafx.util.Pair 实现相同的行为。如果您决定使用 Pair:
menu 数据结构应该如下所示
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));
这是一个递归解决方案，它的工作原理是从预算中递归地减去每件商品的价格，然后将它们放入制造商列表中，直到预算达到 0。如果恰好达到0，您将其添加到列表中。如果它达到负数，则跳过它。
为避免冗余，您提供了一个索引来检查从该索引开始的所有项目。这将防止算法添加相同但顺序不同的 [Fruit, Salad] 和 [Salad, Fruit]。
public static List<List<String>> getListOfBuyableItems(
List<Pair<String, Integer>> menu, double budget) {
List<List<String>> buyableItems = new ArrayList<>();
if (budget != 0 && menu.size() != 0)
keepBuying(menu, budget, new ArrayList<>(), buyableItems, 0);
return buyableItems;
}
public static void keepBuying(
List<Pair<String, Integer>> menu,
double budget,
ArrayList<String> itemBuilder,
List<List<String>> buyableItems,
int index) {
for (int i = index; i < menu.size(); i++) {
Pair<String, Integer> item = menu.get(i);
itemBuilder.add(item.getKey());
int price = item.getValue();
if (budget - price == 0)
buyableItems.add(new ArrayList<>(itemBuilder));
else if (budget - price > 0)
keepBuying(menu, budget - price, itemBuilder, buyableItems, i);
itemBuilder.remove(item.getKey());
}
}
如果您的预算高得离谱或者您要运行这种方法很多次，您可能需要考虑动态规划方法。
上述问题的解决方法在Swift5 :)
func getListOfBuyableItems(_ menu: [String: Double], _ budget: Double) -> [[String]] {
var allList = [[String]]()
var list = [String]()
let menu = menu.map{ (item: [=10=].key, cost: [=10=].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"]]