A zoo keeper wants to place as many different animals in a large pen as possible. The zoo keeper wants to avoid putting animals in the same pen that...

A zoo keeper wants to place as many different animals in a large pen as possible. The zoo keeper wants to avoid putting animals in the same pen that do not get along. If there are n different animals to choose from (1 through n), we construct a n x n matrix whose entries masure how much any pair of animals clash. A clash value of 0 means the animals can live perfectly together whereas a clash value of 1 means one will kill the other. Let ZOO-KEEPER = {<n,M,p,k> | n= number of animals, M is n x n clash matrix, we can place k animals in a pen with penalty <= p}. Prove that ZOO-KEEPER is NP-Complete