选择成本最低的组合 [英] Selecting A combination of minimum cost

问题描述

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

 休闲项目价格
    ----------------------
    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的

我无法设计出这样做或没有得到的想法如何做有效的方法？你知道吗？

更新

下面我的对象是什么样子

 类休息{
  地图＆LT;字符串，整数＆GT;菜单; //项目，价格地图
}
 

解决方案

这个问题是 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 40

Now 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).

这篇关于选择成本最低的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！