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).
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…