Buenas tardes, me mandaron de tarea este algoritmo y no se como resolverlo.
Ejercicio 1) Ken y Barbie
Luego de años de feliz matrimonio, Ken y Barbie han decidido divorciarse y dividir sus propiedades en forma pareja. Cada una de sus N mansiones tiene un valor entre 1.000.000 y 40.000.000 dólares. Ken recibirá algunas de esas mansiones, Barbie recibirá otras de esas mansiones y el resto será vendido y repartido en efectivo en partes iguales.
Ni Ken ni Barbie tolerarán que el otro tenga propiedades con mayor valor total, o sea, la suma de las mansiones que recibirá Ken debe ser igual a la suma de las mansiones que reciba Barbie. Como los valores totales serán iguales, Barbie y Ken quieren recibir lo mayor posible en propiedades, minimizando así la venta de mansiones.
Dados los valores de las N mansiones, calcular el valor total de las mansiones que deben ser vendidas.
Ejemplo
Ken y Barbie tienen 5 mansiones valuadas en 6.000.000, 30.000.000, 3.000.000, 11.000.000 y 3.000.000 dólares. Para satisfacer sus requerimientos, Ken (o Barbie) recibirá la mansión de 6.000.000 y el otro recibirá 2 mansiones de 3.000.000 dólares. Las mansiones de 11.000.000 y 30.000.000 dólares deben ser vendidas, por un total de 41.000.000 dólares. La respuesta es 41.000.000.
Primero, implemente una ordenación para el arreglo con los valores. (merge sort)
luego debería ir tomando la casa de mayor valor y ver si puedo armar una suma de las demás que llegue a ese valor....pero no se como seguir.
Me pueden ayudar alguien con mayor conocimiento?
Ejercicio 1) Ken y Barbie
Luego de años de feliz matrimonio, Ken y Barbie han decidido divorciarse y dividir sus propiedades en forma pareja. Cada una de sus N mansiones tiene un valor entre 1.000.000 y 40.000.000 dólares. Ken recibirá algunas de esas mansiones, Barbie recibirá otras de esas mansiones y el resto será vendido y repartido en efectivo en partes iguales.
Ni Ken ni Barbie tolerarán que el otro tenga propiedades con mayor valor total, o sea, la suma de las mansiones que recibirá Ken debe ser igual a la suma de las mansiones que reciba Barbie. Como los valores totales serán iguales, Barbie y Ken quieren recibir lo mayor posible en propiedades, minimizando así la venta de mansiones.
Dados los valores de las N mansiones, calcular el valor total de las mansiones que deben ser vendidas.
Ejemplo
Ken y Barbie tienen 5 mansiones valuadas en 6.000.000, 30.000.000, 3.000.000, 11.000.000 y 3.000.000 dólares. Para satisfacer sus requerimientos, Ken (o Barbie) recibirá la mansión de 6.000.000 y el otro recibirá 2 mansiones de 3.000.000 dólares. Las mansiones de 11.000.000 y 30.000.000 dólares deben ser vendidas, por un total de 41.000.000 dólares. La respuesta es 41.000.000.
Primero, implemente una ordenación para el arreglo con los valores. (merge sort)
luego debería ir tomando la casa de mayor valor y ver si puedo armar una suma de las demás que llegue a ese valor....pero no se como seguir.
Me pueden ayudar alguien con mayor conocimiento?