Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Set Theory Problem
Replies: 1   Last Post: Jan 15, 2010 12:17 PM

 Messages: [ Previous | Next ]
 Pete Posts: 1 From: England Registered: 5/6/09
Set Theory Problem
Posted: May 6, 2009 4:25 AM

Hi,

I need help with creating an algorithm to solve the problem below in the most efficient manner (efficiency in this case means low processing, not memory)

(Disclaimer: I studied discrete maths as part of my university course, but this was many years ago and I have forgotten most of the correct syntax. Sorry!)

Imagine we have

Set A (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
Set B (3,3,4,5,5,5,5,5,6,6,7,8,12)
Set C
(
Set C.A (1,2) = 10
Set C.B (1,4,3) = 15
Set C.C (3,4,5) = 20
Set C.D (3,3,4,5) = 25
Set C.E (5,6) = 10
Set C.F (5,5,6) = 10
Set C.G (3,3,4,5,5,5,5,5,6,6,7,8,12) = 5
)

B is a subset of A
C is a subset of A

I need to find
1) Which C are in B
2) What is the best combination of C. (Best means the biggest value i.e. C.A is worth 10, C.B is worth 15 etc)

When a C is found in B; B is to be reduced by C (e.g. if C.G is applied to B, there will nothing left in B)
A single instance of C can be applied to B a number of times (e.g. C.E above is in B twice)

Assume I have done 1 and the method is called GetApplicableSets(SetB) and the example above would return C.C, C.D, C.E, C.F, C.G

How do I do 2?

Date Subject Author
5/6/09 Pete
1/15/10 yosi111