我在不同的餐厅有不同项目的数据
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和S，创造你的问题的一个实例，一个餐厅，使得价格每个项目的S（这是一组的一个或多个项目）为1。
现在，为您的问题提供最佳解决方案-可能的最低价格，基本上就是覆盖“宇宙”所需的最小子集数量。
给定解决布套问题的最佳方法-所需的布套数量是子集的最小价格。
结论：
由于我们已经看到有效解决此问题将有效解决SCP，因此我们可以得出结论，问题是NP-Hard，因此没有已知的多项式解决方案（并且大多数人认为不存在）。
替代方案是使用启发式解决方案或蛮力解决方案（只需在指数时间内搜索所有可能性）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句