选择最低成本的组合

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

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
}

Answer 1

这个问题是NP-Hard.我将从套装封面问题中减少.

设置封面问题(SCP):
给定一系列元素U(在你的例子中U={dosa,idly,upma})和一组子集U,让它S(例如S={{dosa}, {idly,upma}, {upma}})找到最小数量的子集,S使它们的联合等于U.

减少:
给定一个封面问题,U并S在一个餐馆创建一个问题实例,这样每个项目的价格S(这是一个或多个项目的集合)是1.

现在,给出问题的最佳解决方案 - 尽可能最低的价格,基本上是覆盖'宇宙'所需的最小子集数量.
给定集合覆盖问题的最优解决方案 - 所需集合的数量是子集的最小价格.

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

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