Recently I got to thinking about a problem and I wondered what sort of algorithm could be used to solve it.
Here’s the basic problem :
You have two sets of items, call them P and Q. For each item in each set, you also know whether it ‘matches’ with a particular item in the other set (and a ‘match’ is reciprocal, so if P[sub]5[/sub] matches with Q[sub]37[/sub], then Q[sub]37[/sub] matches with P[sub]5[/sub]).
The object is to pick two smaller subsets of the lists which maximize the number of matches between the smaller sets.
Here’s an example. Suppose you are in charge of coming up with an automatic candy making machine. The machine will randomly pick a flavoring and a coloring to mix in each candy (so you can get red-nectarine, chartreuse-chocolate, etc.). Some of the flavorings and colorings, however, just don’t mix well chemically, and make the candy taste bad. Now, you have a long list of flavorings, and a long list of colorings, and you know how they combine, but the machine can only hold 20 of each. You need to pick the 20 flavors and colors that produce the fewest number of bad candies as possible (The number doesn’t have to be the same; you could have 25 colors and 31 flavors, for example).
My questions, especially for those who know a lot about algorithms are –
Does it seem like this problem has optimal solutions that can be found analytically?
I came up with a algorithm for finding a solution, and I think it’s optimal (the solution, not the algorithm) but I’m not entirely sure. I’ll post it later but I’m wondering what else is out there already.
Also, what about expanding this for when the matches are not perfect? (Like, marketing shows that purple-tomato is popular with 60% of people, and green-popcorn only 20%).