Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
October 9th, 2009, 03:30 AM
 noob_devshed
Registered User

Join Date: Oct 2009
Posts: 1
Time spent in forums: 2 m
Reputation 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
October 9th, 2009, 02:44 PM
 jwdonahue
Contributing User

Join Date: May 2004
Posts: 3,417
Time spent in forums: 3 Weeks 5 Days 12 h 51 m 9 sec
Reputation Power: 886
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.
__________________
I no longer wish to be associated with this site.

Last edited by jwdonahue : October 9th, 2009 at 02:48 PM.

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Algorithm for finding out the cheapst combination