java - 选择成本最低的组合

Question

我有不同餐厅不同元素的数据

    Rest    Item     Price
    ----------------------
    ABC     dosa      14
    ABC     idly      30
    ABC     idly+upma 25

    123     dosa      30
    123     idly      7
    123     upma      12

    XYZ     dosa      20
    XYZ     idly      12
    XYZ     upma      20
    XYZ     dosa+upma 30
    XYZ     dosa+idly+upma 40

现在我需要选择一家能给我提供最优惠“dosa+idly+upma”商品的餐厅。

从上面的例子来看:它将是餐厅“ABC”

我无法设计出有效的方法来执行此操作，或者不知道该怎么做？有什么想法吗？

更新

这是我的对象的样子

Class Rest{
  Map<String,Integer> menu; //item,price map
}

Answer 1

这个问题是NP-Hard 。我将显示 Set Cover Problem 的减少.

布景问题 (SCP):
给定一个元素宇宙U (在您的示例中 U={dosa,idly,upma} )和 U 的一组子集, 让它成为 S (例如 S={{dosa}, {idly,upma}, {upma}} )找到 S 的最小子集数这样他们的联合等于U .

减少:
给定封面问题 U和 S , 创建一个餐厅问题的实例，例如 S 中每个项目的价格 (这是一组一个或多个项目)是 1。

现在，给定您的问题的最佳解决方案 - 可能的最低价格基本上是覆盖“宇宙”所需的最少子集数。
给定集合覆盖问题的最优解——所需集合的数量是子集的最小价格。

结论:
由于我们已经看到有效地解决这个问题将有效地解决 SCP，我们可以得出结论，该问题是 NP-Hard，因此没有已知的多项式解决方案(并且大多数人认为不存在)。

替代方法是使用启发式解决方案或蛮力解决方案(只需在指数时间内搜索所有可能性)。