elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Problema Programación Dinamica
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Problema Programación Dinamica  (Leído 2,247 veces)
maxisolis

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Problema Programación Dinamica
« en: 28 Junio 2015, 22:28 pm »

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?


« Última modificación: 28 Junio 2015, 22:34 pm por maxisolis » En línea

maxisolis

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Re: Problema Programación Dinamica
« Respuesta #1 en: 28 Junio 2015, 22:36 pm »

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];
            }
         }
      }
   }
   
}


En línea

robertofd1995

Desconectado Desconectado

Mensajes: 172


Ver Perfil
Re: Problema Programación Dinamica
« Respuesta #2 en: 29 Junio 2015, 00:29 am »

Donde te da el error ?,al ordenar ?

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

maxisolis

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Re: Problema Programación Dinamica
« Respuesta #3 en: 29 Junio 2015, 02:19 am »

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
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
1 muestra del poder de la programacion dinamica « 1 2 3 »
.NET (C#, VB.NET, ASP)
spiritdead 23 12,224 Último mensaje 19 Enero 2015, 23:01 pm
por Eleкtro
Programación Dinámica
Java
erikcdlm 0 1,738 Último mensaje 7 Noviembre 2014, 20:32 pm
por erikcdlm
problema de backtracking y programacion dinamica
Programación C/C++
aprendiz de programador 6 5,369 Último mensaje 12 Diciembre 2015, 16:08 pm
por SnzCeb
[Estrategias] Programación Dinámica vs Divide y conquistarás (DUDA)
Programación C/C++
GGZ 4 4,137 Último mensaje 7 Noviembre 2016, 08:20 am
por GGZ
Ackermann - Programacion Dinámica
Programación C/C++
GGZ 4 2,854 Último mensaje 12 Febrero 2017, 14:35 pm
por GGZ
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines