Reference no: EM132517929

Assignment Task - Well, this is the problem with letting everybody decide their own project. It turns out people found out about an experimental quantum computer in the basement, and at least half of the groups want to do quantum computing research on it. The director wisely decides that different groups should actually be researching different things, and that they aren't going to buy extras of the expensive equipment they already have. With some discussions, inventories of equipment, and sharing of potential research ideas, each group comes up with a list of research projects they would be willing to pursue, and for each one, a list of equipment that they will need. Using a machine-learning screening and classification on the proposals, the director weeds out the bad projects, and separates those remaining into categories, with the goal that no more than one project in each category should be pursued at once.

Give an efficient algorithm to select which projects should be selected for research, or prove that the problem is NP-complete. Your inputs are the proposals (which group is making the proposal, what category of project their proposal is, and the list of resources needed to complete the research), and you must select a set of projects such that each group has exactly one selected project, no two projects from the same category are selected, and no limited resource is assigned to more than one of the projects selected.