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 .
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.
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 Σwm value is minimal ... until we have only two groups . Don't work , I can easily find counterexamples .