我在不同的餐厅有不同项目的数据
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 Set Problem的减少。
集合覆盖问题(SCP): 给定一个元素宇宙U(在您的示例中U={dosa,idly,upma})和的子集的集合U,让它成为S(例如S={{dosa}, {idly,upma}, {upma}})找到其子集S等于的最小子集数U。
U
U={dosa,idly,upma}
S
S={{dosa}, {idly,upma}, {upma}}
减少: 给定一个集合覆盖问题同U和S,创造你的问题的一个实例,一个餐厅,使得 价格 每个项目的S(这是一组的一个或多个项目)为1。
现在,为您的问题提供最佳解决方案-可能的最低价格,基本上就是覆盖“宇宙”所需的最小子集数量。 给定解决布套问题的最佳方法-所需的布套数量是子集的最小价格。
结论: 由于我们已经看到有效解决此问题将有效解决SCP,因此我们可以得出结论,问题是NP-Hard,因此没有已知的多项式解决方案(并且大多数人认为不存在)。
替代方案是使用启发式解决方案或蛮力解决方案(只需在指数时间内搜索所有可能性)。