CODEWITHSUNDEEP
algorithmgroupingdynamic-programmingpartitioningnp
jon
jon

Reputation: 53

How to determine optimal grouping?

Problem: Given elements and sets that the elements can corespond to, find optimal division these elements to sets, such that number of sets is minimal.

Example:

'a' : (1, 2),
'b' : (1, 3),
'c' : (3, 5),
'd' : (2, 6)

This input means that a can be only in set 1 or set 2, b can be only in set 1 or set 3 and so on.

This example should give an answer of 2 with sets: set number 2 and set number 3. As we can put a and d into set 2 and b and c into set 3. That is the optimal partitioning.

Is this well known problem? Or maybe NP-hard problem? Anybody know how to approach or solve it?

Upvotes: 0

Views: 54

Answers (0)

Related Questions