0

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

iouvxz
  • 121
  • 4
  • (although this is still not a question, but at least it does demonstrate some effort) – Hulk Jul 19 '16 at 10:49
  • 1
    Can you clearly state what you need help with? From what I can gather this is what you tried so far and neither seems to work? – maple_shaft Jul 19 '16 at 11:26

1 Answers1

1

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.

maple_shaft
  • 26,401
  • 11
  • 57
  • 131
  • Could you please explain why it is np hard ? I read Optimization problem ,but I still don't how to prove it's np hard ,like reduce a known NP-complete problem to my problem. – iouvxz Jul 20 '16 at 02:00
  • @iouvxz If you need something like a mathematical proof for say a homework assignment then I probably cant help you. I only know it is NP hard because the decision of the right answer must be compared to all combinations of k. Oppose this to say Insertion Sort where my decision is only based on the item I am next until I arrive at my answer. I dont have to look at every combination of an ordered list to find the one that is sorted. All I can do in this problem is optimize it so that I can sometimes perform less operations for true or false while I traverse all combinations of k. – maple_shaft Jul 20 '16 at 02:11
  • @iouvxz If you want a proof for np hard you might want to ask for help on CS Stackexchange. We help with algorithms on this site but we are more focused on practical software engineering and less on pure computer science. – maple_shaft Jul 20 '16 at 02:13
  • 1
    "I only know it is NP hard because the decision of the right answer must be compared to all combinations of k" , no ,you can't say that .I don't need a full proof , but you at least should reduce a known NP-complete problem to my problem , that's the only way you can declare a problem is np hard. – iouvxz Jul 20 '16 at 05:32
  • @iouvxz Quite right, I can't say that. It is just my intuition guessing this is NP hard. Good luck. – maple_shaft Jul 20 '16 at 13:46