Foro de elhacker.net

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?

tengo este código implementado:


/Función principal
nat Sistema::RepartirMansiones(Array<nat> valorMansiones)
{
   nat retorno=0;
   nat inicio=0;
   nat fin= valorMansiones.Largo-1;
   nat medio=inicio+fin/2;
   ordenar(valorMansiones,inicio,medio,fin);
   for (int i=valorMansiones.Largo; i>=0; i--){
      if(valorMansiones!=0){
         if(PDinamicaProblemaSuma(valorMansiones, valorMansiones.Largo,valorMansiones)){
         valorMansiones=0;
         //falta marcar con 0 (como usadas) las casas que se utilizaron para formar el valor de la mayor)
         }
      }
   }
   
   return 0;
};


// algoritmo que ordena el arreglo
void Sistema::ordenar(Array<nat> valorMansiones, nat inicio, nat medio, nat fin) {
   Array<nat> aux (medio-inicio+1);
   for(nat j=inicio; j<=medio; j++){
      aux[j-inicio] = valorMansiones[j];
   }
   nat c1=0;
   nat c2=medio+1;
   for(nat j=inicio; j<=fin; j++) {
      if(aux[c1] < valorMansiones[c2]) {
         valorMansiones[j] = aux[c1++];
         if(c1==medio-inicio+1){
            for(nat k=c2; k<=fin; k++){
               valorMansiones[++j] = valorMansiones[k];
            }
         }
      }
      else {
         valorMansiones[j] = valorMansiones[c2++];
         if(c2==fin+1){
            for(nat k=c1; k<=medio-inicio; k++){
               valorMansiones[++j] = aux[k];
            }
         }
      }
   }
   
}

Donde te da el error ?,al ordenar ?

y el metodo PDinamicaProblemaSuma(valorMansiones, valorMansiones.Largo,valorMansiones) ? ese es el que quieres implementar ?

al ordenar no me da problemas.
Lo que no se como implementar es el algoritmo que realiza la suma resultado equivalente al valor mas grande que va quedando en el arreglo.
tenes idea como puedo implementarlo?

se que es con el algoritmo de suma subconjuntos