Find the best combination of sets?

[PeteSpeed]

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,2 0)
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?

[r035198x]

Lets clean up some things first.
A Set contains unique elements. So B can't be called a Set.
Also could you describe what Set C is all about. What elements make up Set C and what does Set C.A (1,2) = 10 mean?

[PeteSpeed]

Hi r035198x,

What I mean with B is a subset of A. (is that all of the values in C must be in A).

What I am trying to get regarding C is that there are many of them, some have a higher value (to give this context I am working with money). So I want the BEST* combinations of C.

*BEST - as in the highest values when added together.

Another way of putting it is I am trying to find the combination of C.x sets which together are a subset of B, with the highest summed values. Am I making sense yet?

Further investigation has led me to Knapsack Problem and Subset sum problem. What I am trying to do is related to these but is subtly different I think.

Thanks for taking the time of reading my post.

[r035198x]

Please read my post again and respond to what I have posted.
You need to be able to explain the problem using the correct terminology if you are going to get help.
Perhaps you should get a text/tutorial that explains the right terminology and read up that first and then you can polish up your description.

[PeteSpeed]

Sorry, can you tell me the parts that I am not describing very well?

[PeteSpeed]

Instead of sets, think of them as arrays

[JosAH]

@PeteSpeed
Please re-read what you have posted: set C isn't shown so your entire example doesn't make sense. Please preview before you post.

kind regards,

Jos

[jkmyoung]

So A is all items
B has a certain quantity of each member in A.
C is a set of groups of quantities of each member in A.

Linear Programming:
Call N.A the number of times you use C.A, N.B the number of times you use C.B, etc..
Let V.A be the value of C.A, V.B be the value of C.B etc,

Maximize Sum(for all i) N.i * C.i
where:
R1: N.A + N.B <= 0
R2: N.A <= 0
R3: N.B + N.C + 2N.D + 2 N.G <= 2
R4: N.B + N.C + N.D + N.G <= 1
etc.. for all 20 elements of A.
And N.A, N.B, ... >= 0

Note that you have mutltiple optimal answers with values of 45
N.D = 1, N.E = 2 down the line to
N.D = 1, N.F = 2

=================
There's all sorts of algorithms you can use to find local maximums, generally based on some sort of greedy algorithm. Some of these steps may be harder to program than others, so pick and choose which ones you want to use.

I would advise first, optimizing the problem. Eliminate any variables which are unnecessary.
Step 1 Elimination: eliminate any elements which can't be used.
Leaves us with (3,4,5,6,7,8,12)

Step 2 Eliminate unnecessary elements.
3 is only used when 4 is also used.
ratio of 3:4 is from 1 - 2 in all sets of C
ratio of 3:4 in set B is 2
So whenever we use a 4, we use at most 1 3.
-> We can eliminate element 3

4 is only used whenever 5 is also used.
ratio of 4:5 in set B is 1/5
ratio of 4:5 in sets of C ranges from 0 - 1
1 > 1/5, we cannot eliminate 4 yet.

etc..
we eliminate elements 7, 8 and 12 in this way also. This leaves us with
B' (4,5,5,5,5,5,6,6)
C.C' (4,5) = 20
C.D' (4,5) = 25
C.E' (5,6) = 10
C.F' (5,5,6) = 10
C.G' (4,5,5,5,5,5,6,6) = 5

Step 3: Minimize sets.
If we did this from the get go, in real life situations, the odds are low that there would be many sets to meaningfully reduce. However, after element minimization, we can remove some of the reduced sets.
After this optimization, we can also see that sets C.C', C.F', and C.G' are unnecessary.
C.D' is contained within C.C', and has equal or higher value
C.E' is contained within C.F', and has equal or higher value
C.F', is contained within C.G', and has equal or higher value.

Repeat Step 2 and Step 3 as much as necessary. Then solve.

B' (4,5,5,5,5,5,6,6)
C.D' (4,5) = 25
C.E' (5,6) = 10
From here, you can easily get N.D = 1, N.E = 2

Hope something in this helps.