hulk_baba's blog

Maximum number of people one can invite
By hulk_baba, history, 7 years ago, In English

While solving a problem I thought of another problem which could have easily been asked in the earlier problem and is as follows: Consider an array of a group of people of size n. One wants to invite the maximum number of people given to m constraints that a group X and a group Y cannot be invited together.

Example:- Group No. 1 2 3 4 5 6 Size of group 3 4 7 2 8 10

Suppose m=3 and X=1, Y=6. X=2, Y=4. X=1, Y=5. I don't know the answer but it can be calculated for small cases like these but I thought a lot about formulating it as a dynamic programming problem but couldn't reach anywhere. Any help is appreciated.

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could you clarify if what you mean is that you have people seperated into some groups and you know that you can't invite people from some of the groups at the same time? If so then a simpler version of this problem(with additional constraint) is Sophie from XIII POI .

If you want to actually find the maximal possible number of people you can invite then I think that this becomes an NP problem.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It means for the given case above that one can not invite group no.1 and group 6 together only one of them or none of them can be invited (whatever choice gives the maximum number of people) similarly for group 2 and group 4 and so on so they should not be present together.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Alright, that's what I thought. Simply substitute groups with one person(add weight or smth) and that's pretty much the same problem as the one I've linked only without additional constraints. I belive it to be NP hard but if It's not I'd gladly learn about it.

      → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Pretty sure this is equivalent to the maximum independent set problem, if you just consider the groups as vertices in a graph and create an edge between groups that cannot be invited together. This would make it NP hard.

→ Reply