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

Answer 2

A sketch of one possible greedy algorithm is:

1. Iterate through all unary offers (e.g. dosa, idly or upma) to find the minimum of each.
2. Iterate through all binaray (e.g. idly+upma) / tertiary (...) offers, compare if it's cheaper than the unary offers and replace if so.

You will have to code the offer deparsing still, but it shouldn't be that hard. This algorithm will find good, but not necessary the best solution, and might work on very small smaples.

Actually, your problem compares to the Rucksack or TSP problems, which are NP-complete and thus only solvable in exponentially time. If you want a solution for that, consider reading a lot of papers and coding even more. That's the holy grail of computer science. ;-)

UPDATE: On request of the TO here's some exponentially pseudocode sketch:

foreach restaurant
    create a list of all possible combinations of the offers // here's the exp!
    filter those combinations that hold more/less than 1 dosy/idly/umpa
    select minimum of the remaining ones

Comment: This is really ugly, yuk! :-(

Answer 3

try

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Mult {
    /**
     * @param args
     */
    public static void main(String[] args) {
        Map<String,List<X>> xx = new HashMap<String,List<X>>();
        xx.put("ABC",new ArrayList<X>());
        xx.get("ABC").add(new X("", 0));
        xx.get("ABC").add(new X("dosa", 14));
        xx.get("ABC").add(new X("idly", 30));
        xx.get("ABC").add(new X("idly+upma", 25));


        xx.put("123",new ArrayList<X>());
        xx.get("123").add(new X("", 0));
        xx.get("123").add(new X("dosa", 30));
        xx.get("123").add(new X("idly", 7));
        xx.get("123").add(new X("upma", 12));


        xx.put("XYZ",new ArrayList<X>());
        xx.get("XYZ").add(new X("", 0));
        xx.get("XYZ").add(new X("dosa", 20));
        xx.get("XYZ").add(new X("idly", 12));
        xx.get("XYZ").add(new X("upma", 20));
        xx.get("XYZ").add(new X("dosa+upma", 30));
        xx.get("XYZ").add(new X("dosa+idly+upma", 40));

        String[] t = {
                "dosaidlyupma",
                "idlydosaupma",
                "upmaidlydosa",
                "dosaupmaidly",
                "upmadosaidly",
                "idlyupmadosa"};
        Set<String> targets = new HashSet<String>(Arrays.asList(t));

        Map<String,Integer> best = new HashMap<String,Integer>();

        for(String restaurant:xx.keySet()){
            best.put(restaurant, Integer.MAX_VALUE);
            String combo = null;
            for(X a:xx.get(restaurant)){
                int deal = a.price;
                combo = a.item;
                for(X b:xx.get(restaurant)){
                    deal = deal + b.price;
                    combo = combo + "+" + b.item;
                    for(X c:xx.get(restaurant)){
                        deal = deal + c.price;
                        combo = combo + "+" + c.item;
                        if (targets.contains(combo.replaceAll("\\+", ""))){
//                          System.out.println(restaurant+"\t"+combo.replaceAll("\\+", "")+"\t"+deal);
                            if (best.get(restaurant) > deal){
                                best.put(restaurant, deal);                 
                            }
                        }
                    }
                }
            }
        }

        System.out.println(best);
    }

}

will give you

{XYZ=40, ABC=39, 123=49}

it's the old good brute force approach.

not the best one, but for this small set, it works.

Answer 4

1. Calculate the possible price combinations: Iterate through the map and parse the strings. Store each price combination.

2. Filter out the more expensive prices.

3. Compare the remaining prices at each restaurant, and return the restaurant with the cheapest price.

You could also do some checks to minimise iterations, e.g:

• If idly is > than idly+umpa, don't calculate the any combinations involving idly.

Answer 5

First you need to make all the possible combination of 3 items corresponding to different restaurents like :

XYZ     dosa+idly+upma 52
XYZ     dosa+upma+idly 42
XYZ     dosa+idly+upma 40

Same the above case with all the restaurants.

Then sort the price and let the minimum price restra WIN.