我有不同的项目在不同的餐厅数据。
休闲项目价格 ---------------------- ABC DOSA 14 ABC袖手旁观30 ABC袖手旁观+ UPMA 25 123 DOSA 30 123袖手旁观7 123 UPMA 12 XYZ DOSA 20 XYZ袖手旁观12 XYZ UPMA 20 XYZ DOSA + UPMA 30 XYZ DOSA +袖手旁观+ UPMA 40
现在我需要拾取一个餐厅,给了我最好的交易的DOSA +袖手旁观+ UPMA项目。
从上面的例子:这将是餐厅ABC的
我无法设计出这样做或没有得到的想法如何做有效的方法?你知道吗?
更新
下面我的对象是什么样子
类休息{ 地图<字符串,整数>菜单; //项目,价格地图 }解决方案
这个问题是 NP难 。我将展示从集合覆盖问题的下降。
集合覆盖问题(SCP): 给定元素的宇宙 U (在你的榜样 U = {DOSA,懒懒地,UPMA} )和一组 U 的子集,让它成为取值(例如 S = {{ DOSA},{袖手旁观,UPMA},{UPMA}} )找到最小的数的S子集,使得他们的工会平等 U 。
的减少: 给定一个集合覆盖问题与 U 和取值,创建你的问题的一个实例和一个餐厅,这样的该价格每个项目的的在取值(这是一组的一个或多个项目)为1。
现在,给出一个最佳的解决问题的方法 - 按最低价格有可能,基本上是需要覆盖的'宇宙'子集的最小数量。 给定一个最佳的解决方案的集合覆盖问题 - 所需组的数目是所述子集的最小价格
结论: 既然我们已经看到了解决这一问题的有效将有效地解决SCP,我们可以得出结论,这个问题是NP难,因此没有已知的多项式的解决方案,它(和大多数人相信一个不存在的话)。
替代品使用的是启发式的解决方案或蛮力一(只是搜索所有的可能性,在指数时间)。
I have data of different items in a different restaurants
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 40Now I need to pickup a restaurant which gives me the best deal of "dosa+idly+upma" items.
From the above example: it will be restaurant "ABC"
I am unable to design efficient way of doing this or not getting idea on how to do? Any idea?
Update
Here how my objects look like
Class Rest{ Map<String,Integer> menu; //item,price map }解决方案
This problem is NP-Hard. I will show a reduction from the Set Cover Problem.
Set Cover Problem (SCP): Given a universe of elements U (in your example U={dosa,idly,upma}) and a set of subsets of U, let it be S (for example S={{dosa}, {idly,upma}, {upma}}) Find the smallest number of subsets of S such that their union equals U.
The reduction: Given a Set Cover Problem with U and S, create an instance of your problem with one restaurant, such that the price of each item in S (which is a set of one or more items) is 1.
Now, given an optimal solution to your problem - the minimal price possible, is basically the minimal number of subsets needed to cover the 'universe'. Given an optimal solution to the set cover problem - the number of sets needed is the minimal price of the subset.
Conclusion: Since we have seen that solving this problem efficiently will solve SCP efficiently, we can conclude that the problem is NP-Hard, and thus there is no known polynomial solution to it (and most believe one does not exist).
Alternatives are using a heuristic solution or a brute force one (just search all possibilities, in exponential time).
更多推荐
选择成本最低的组合
发布评论