Selecting A combination of minimum cost
algorithm, java, minimum
Solution
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).
Problem
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 } ```