### Thread: Algorithm for finding out the cheapst combination

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2009
Posts
1
Rep Power
0

#### Algorithm for finding out the cheapst combination

Hello, I have a few sets which are like

SET A(1,2,3,11,10) - \$30
SET B(2,5,8) - \$20
SET C(6) -\$25
SET D(6,8) -\$30
SET E(7,5) -\$20
SET F(5,6,7,8,9,10) -\$60
.
.
.

and so on... All are random, Now consider sets D,E and F I want to buy the cheapest combination for a set, SET Q(7,8,6,5) the answer should be SET D + SET E, not the SET F

2. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
891
First eliminate all sets that have members that aren't in Q. Sort the remaining sets by size, insert the remaining sets that equal to Q into a binary tree of sets of set references (is there a faster structure for this? Hash table perhaps?) then starting with the largest sets that aren't equal to Q, search for single sets that will complete them, then search for pairs of sets that will complete them, etc., building up the tree. Note that the search would be limited to size(Q) - size(s), no point in trying combinations that would exceed the length of Q. Then visit all the nodes, inserting into a sorted list based on total cost of the sets in that node. The cheapest combination will be on one end of that list.

We're talking NP Complete here so if the total number of sets is high enough, the Universe might expire before you get the result (assuming you have sufficient storage space, which itself could increase the entropy of the Universe substantially).

You might have to alter your criteria to "cheap enough" rather than "cheapest". For instance, after eliminating sets that have members not in Q, you could do a statistical analysis of the costs of the individual sets to get some figure of the expected distribution of costs, and then pick a point somewhere in the middle and when you find a combination that is lower than that point, just quit searching.

Also, you might find it's acceptable to buy a set that has extra members! Particularly if you can sell off that extra unit. But this just makes the problem even harder to solve if cheapest is indeed the only acceptable goal.

Good luck! Wish I had more time to dive into this one.
Last edited by jwdonahue; October 9th, 2009 at 01:48 PM.