这是一个使用递归的解决方案。
为了简化操作，我定义了一个 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>(),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]
,
这个问题是Coin Change问题的直接应用。
动态规划解决方案可以递归构建如下：
对于每一项，解决方案是两种情况的组合：
- 该项目包含在解决方案中
- 该项目已排除
对于第一种情况，解决方案是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]
,
以一种非常非常低效的方式 - 我认为它类似于 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"],"Fries"],["Mozzarella"],["Salad"]]
,
在这种情况下，multiset 由适合特定预算的菜单项的多个组合组成。菜单项可以重复，并且排列组合被认为是相同的，例如[a,a,b,c] 和 [c,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() 组合映射的字符串表示。
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 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]=8.60]
[[Fries,Plate]=8.55,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,Fruit]=7.65
[Fries,Fruit]=4.90
[Fries,Fruit]=7.50
[Fries,Salad]=8.25
[Fries,Wings]=8.45
[Fries,Mozzarella]=6.95
[Fries,Salad]=6.10
[Fries,Wings]=6.30
[Fruit]=2.15
[Fruit,Fruit]=4.30
[Fruit,Fruit]=6.45
[Fruit,Mozzarella]=8.50
[Fruit,Salad]=7.65
[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
,
正如其他解决方案中所指出的，最好以美分存储价格以避免四舍五入错误。
此外，由于不需要通过键获取值，您可以创建一个新类来存储 Item/Price 对或使用 Pair 类使用 import javafx.util.Pair 来实现相同的行为.如果您决定使用 menu，您的新 Pair 数据结构应如下所示：
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,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,i);
itemBuilder.remove(item.getKey());
}
}
如果您的预算高得离谱，或者您要多次运行此方法，您可能需要考虑动态编程方法。
