Java - Boda

   
Vista:

Boda

Publicado por Rolando (2 intervenciones) el 14/01/2010 05:47:25
Para una boda tenemos una lista de n personas que pueden ser invitadas o no. Pero no todas pueden serlo, ya que existen enemistades conocidas entre ellas, que debemos evitar. Las enemistades conocidas vienen dadas como pares (a1, b1), (a2, b2),…, (ak, bk), indicando cada par i-ésimo que ai y bi son enemigos conocidos. Aplicando transitividad, los enemigos de una persona i son todos los enemigos conocidos de i y los enemigos de sus amigos. Decimos que los amigos de una persona son todos los enemigos de sus enemigos.
Una persona asistirá a la boda si es invitada y son invitados todos sus amigos y no es invitado ninguno de sus enemigos. El objetivo del problema es decidir la lista de invitados de manera que se maximice el número de asistentes a la boda.
Diseñar un algoritmo para resolver el problema, justificando razonadamente su funcionamiento. Acotar el orden de complejidad del algoritmo diseñado. Mostrar la ejecución sobre el siguiente ejemplo.
Posibles invitados: n = 8
Enemistades conocidas: (1,2), (5,7), (6,8), (1,4), (2,7)

Nota: Aplicando las definiciones es posible, en algún caso, que dos personas sean a la vez amigos y enemigos. En ese caso ninguno de ellos puede ser invitado.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:Boda

Publicado por James (207 intervenciones) el 15/01/2010 05:25:18
Bueno chevere explicaste bien tu necesida, ahora cual es tu duda?, si pretendes que alguien te de haciendo tu programa lo veo dificil, por no decirlo imposible.

Mira te explico como funciona se supone que tu realizas una pregunta especifica y alguien con un mayor conocimiento o experiencia te ayuda a resolver tu problema, pero si quieres que alguien te de haciendo tus tareas creo que por aca no lo conseguiras, en todo caso intenta realizar tu aplicacion(al menos intentalo) y cuando en algun punto te veas estancado regresa, entonces seguro alguien con gusto te ayuda a resolver tu problema, Suerte
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar