CODEWITHSUNDEEP
algorithm
nik
nik

Reputation: 411

Algorithm that optimally divide objects into given groups with given weights

I don't know how correctly describe the problem, so I will give an example. Basically I want an algorithm that optimally divide objects into given groups. That given groups have given weights. Аs a result, the algorithm should give a set of groups with the maximum total weight. Each object can be only in one group, also object does not have to be in a some group.

Example:

Given objects - o1, o2, o3, o4, o5, o6, o7, o8

Given groups with their weights:

Best solution here is (g6, g7) - it gives (25 + 25) = 50

Some of not best solutions:

Possible solution is:

But I think it will take too long with a lot of groups and objects. Is there a faster solution? I feel like this is some kind of known issue with a known solution - am I right? If not - is there known similar issues that can help?

Upvotes: 0

Views: 917

Answers (1)

Stef
Stef

Reputation: 15505

Consider the weighted graph G, where:

  • The set of vertices V = {g1, g2, ..., g7} is your set of groups;
  • Two groups gi and gj share an edge if and only if their intersection is non-empty (in other words, there exists an object o_k which is in both groups);
  • Each vertex has a weight, which is the weight of the group.

Then your problem is exactly the maximum-weight independent set problem.

This problem is NP-complete in general, but it has been studied a lot. If your instance is small, or if you have additional assumptions, then exact algorithms and approximation algorithms exist.

You do not mention how big your actual problem is. I assume you have more than 7 groups. Here is a solution using integer linear programming: Heuristic to find the maximum weight independent set in an arbitrary graph?

Upvotes: 1

Related Questions