小编典典

选择最低成本的组合

algorithm

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

    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
}

阅读 315

收藏
2020-07-28

共1个答案

小编典典

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

集合覆盖问题(SCP):
给定一个元素宇宙U(在您的示例中U={dosa,idly,upma})和的子集的集合U,让它成为S(例如S={{dosa}, {idly,upma}, {upma}})找到其子集S等于的最小子集数U

减少:
给定一个集合覆盖问题同US,创造你的问题的一个实例,一个餐厅,使得 价格 每个项目的S(这是一组的一个或多个项目)为1。

现在,为您的问题提供最佳解决方案-可能的最低价格,基本上就是覆盖“宇宙”所需的最小子集数量。
给定解决布套问题的最佳方法-所需的布套数量是子集的最小价格。

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

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

2020-07-28