Your given a a list of people and their skillsset. We need to form a team out of these people with as many people as we want. The only condition is each of the skills has a maximum allowed amount in the team formed. i.e Sum of ith skill from all people in the team should be <= Maximum allowed value of the ith skill.
Input starts with 3 integers N S M i.e number of people , total number of skills and total number of edges . Next M lines follow with 3 integers A B C meaning person A has skill B with total amount C. This is followed by S lines with 2 integers X Y where X = skill number and Y = maximum amount of skill X that is allowed to be in the team.
Example Input:
4 2 7
1 1 1
2 1 1
2 2 1
3 1 1
3 2 1
4 2 1
5 2 1
1 2
2 2
Output:
3
In the above example there are multiple options to build a team. We can choose 2,3 to form the team and in this case the total skill = 2 and 2. Person 2 has skills 1 and 2, and person 3 also has skills 1 and 2. We cannot add any more elements since then we will exceed the total skills level allowed in a team. The subset = 1,4,5 or 1,2,5 or 1,3,5 is optimal because the skills level is not breached.
I tried to formulate a maxflow graph but the issue is if a node is chosen then all the edges from it have to be chosen so this wasn't boiling to a network flow graph. I wanted to know if this is a NP-Hard problem and how do we prove that indeed a problem is Np-hard.