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.
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.
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.
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.
Can you provide the solution to the problem you mentioned in the link?
kamilt ?
Yeah, sorry but currently my time is taken by my school and the editorial is in polish only. All I can say is that in this problem you don't use DP. It's a problem that uses theorem about vertex coverage in graphs.
can you please send me the polish editorial, i will use translate. may be that could help
https://oi.edu.pl/static/attachment/20110811/oi13-b5.pdf
good luck :)
which page int the pdf exactly has the solution it's difficult to know
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.