Split k sets to 2 groups of sets

Given k sets ,each contain several elements .

I want to split them to two groups ,

the first group contains m sets ,the second group contain n sets , m + n = k .

Let w1 be the sum of the weights of all the elements in the union of the first group of sets .

and w2 be the sum of the weights of all the elements in the union of the second group of sets .

Design an algorithm to split the k sets to two groups so that w1*m+w2*n has the minimum value .

Algorithm 1:

Set the first group empty ,then keep doing these operations :
moving in a set from group two to group one ;
moving out a set from group one to group two ;
or switch two sets in the two groups ;
each step must not increase the w1*m+w2*n value until we can’t do more operations .
Don’t work , I can easily find counterexamples when this algorithm stops ,the value is not minimal.

Algorithm 2:

First we split the k sets to k groups ,each contains one set .
Then ,split the k groups to k-1 groups so that Σwm value is minimal ,
now the two groups in the same group ,we consider they are always in the same group ,
then split the k-1 groups to k-2 groups so that Σw
m value is minimal …
until we have only two groups .
Don’t work , I can easily find counterexamples .


Assuming Brute Force is not an acceptable approach, your problem is NP Hard, meaning that you cannot effectively solve this for worst case operational complexity. This solution can be optimized though.

This is basically an Optimization Problem. You are required to find the best solution for a discrete set of variables. Granted the number of possible combinations would be enormous potentially but it is certainly discrete.

Specifically this is a Combinatorial Optimization Problem.

Given that there are k sets each with a weight measure. These k sets can only be split in a discrete number of ways (Eg. k = 4 then there are 7 possible distinct combinations of m and n). I am too lazy to do the math for a formula that finds all distinct combinations for any k but that isn’t important unless you would also need to know worst case number of operations.

There is a corresponding Decision Problem in a Combinatorial Optimization. That is for any f(m, n, o), is there ANY solution for f(m, n, o) where o <= 10?

If true then if a solution was = 10 then check remaining solutions where f(m, n, o) where o <= 9?

If true and you encounter say 7 where it is < than 9 then on your next iteration start checking all remaining combinations for <= 6.

If you encounter false after exhausting remaining combinations for 6 then remember those values for m and n being 7 as the best possible for that k.

This can optimize the algorithm and be better than brute force by immediately discarding combinations if mw1 or nw2 are more than o.


Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *