java - 选择最低成本的组合

我在不同的餐厅有不同项目的数据

    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

Now I need to pickup a restaurant which gives me the best deal of "dosa+idly+upma" items.
在上面的示例中:它将是“ABC”餐厅

我无法设计有效的方法来做到这一点，或者不知道如何做？任何想法？

更新

这是我的物体的样子

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

最佳答案

此问题是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，因此没有已知的多项式解决方案(并且大多数人认为不存在)。

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