java - Selecting A combination of minimum cost

Question

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
}

Answer 1

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