20/02/2019, 06:23:08 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: LISTADO ACTUALIZADO DE CURSOS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Problema de longitudes  (Leído 916 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Zar@tuL
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 5


Ver Perfil
« : 03/02/2019, 02:28:03 pm »

     Hola a todos y gracias de antemano por satisfacer mi curiosidad (eso espero) y mantener un lugar como éste donde se usa la cabeza.

El problema es este:
Quiero llegar de un extremo al otro de la mesa de la manera mas precisa posible colocando varios objetos en fila.
Si solo usara lápices iguales dividiría la longitud de la mesa entre la de los lápices y listo.
Pero, si tengo además gomas y bolis, como puedo conocer la combinación más precisa? Y si hay más objetos?

Saludos y gracias.
En línea
manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.846


Ver Perfil
« Respuesta #1 : 03/02/2019, 03:03:09 pm »

Hola Zar@tuL, bienvenido al foro!!

Recordá leer y seguir las reglas del mismo así como el tutorial del [texx]\mathrm\LaTeX[/texx] para escribir las fórmulas matemáticas correctamente.



Con respecto al ejercicio, por favor mostranos tus intentos y errores así podemos ayudarte mejor.

El problema es este:
Quiero llegar de un extremo al otro de la mesa de la manera mas precisa posible colocando varios objetos en fila.
Si solo usara lápices iguales dividiría la longitud de la mesa entre la de los lápices y listo.
Pero, si tengo además gomas y bolis, como puedo conocer la combinación mas precisa? Y si hay mas objetos?

Creo que estás preguntando por, dados unos elementos de mayor o menor longitud, hallar la cantidad mínima de objetos necesarios para cubrir (sin sobrepasar ni que falte) los lados opuestos de una mesa.

En ese caso, mi prueba no es rigurosa pero puedo decirte que se basa en probar y errar.

En primer lugar elegí el objeto más largo que no sobrepase la longitud de la mesa. Realizando un proceso de iteración, andá poniendo en fila el mismo objeto hasta que sobrepase la mesa. El primero que sobrepase lo vas a tener que cambiar por uno más corto, así que volviendo a realizar un proceso iterativo, tenés que ir probando con objetos cada vez más pequeños hasta que encuentres el que se ajuste a la mesa, pero el beneficio fue que usaste los objetos más largos para cubrir la longitud de la mesa.

Saludos
En línea
martiniano
Pleno*
*****

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 649


Ver Perfil
« Respuesta #2 : 03/02/2019, 05:50:15 pm »

Hola.

Os puede interesar el problema de la mochila.

Saludos.
En línea
Zar@tuL
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 5


Ver Perfil
« Respuesta #3 : 04/02/2019, 04:59:34 pm »

     Hola manooooh, gracias por colaborar.

Lo del ensayo y error está bien pero lo que yo busco es una solución matemática y genérica, válida para cualquier longitud.

Voy a intentar plantearlo como tú:
Dada una longitud cualquiera y unos elementos de diferentes longitudes, hallar la combinación con menor número de elementos cuya suma de longitudes mas se aproxime a la longitud dada. Se pueden repetir elementos.

En cuanto a mis intentos no han ido mas allá de plantearme como meterle mano. Por aquello de las repeticiones pensé en combinatoria pero no...

     @ martiniano
Interesante... Sería algo parecido al problema de la mochila no acotado?

Saludos.
En línea
martiniano
Pleno*
*****

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 649


Ver Perfil
« Respuesta #4 : 04/02/2019, 07:07:16 pm »

Hola.

Disculpa pero no soy muy experto en el tema. ¿A qué te refieres con lo de no acotado? ¿Tienes infinitos objetos de cada tipo?

Saludos.

En línea
Zar@tuL
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 5


Ver Perfil
« Respuesta #5 : 04/02/2019, 07:25:42 pm »

Hola.

Disculpa pero no soy muy experto en el tema. ¿A qué te refieres con lo de no acotado? ¿Tienes infinitos objetos de cada tipo?

Saludos.



Exacto. En el supuesto inicial podríamos usar tantos lápices, gomas, etc. como fueran necesarios.

Saludos.
En línea
martiniano
Pleno*
*****

Karma: +0/-0
Conectado Conectado

Sexo: Masculino
España España

Mensajes: 649


Ver Perfil
« Respuesta #6 : 05/02/2019, 03:40:54 am »

Hola.

No creo que ese detalle afecte demasiado al aplicar el algoritmo. Si divides la longitud de la mesa entre la longitud de un lápiz y haces su parte entera no vas a poder utilizar más de esos lápices, por lo que te da igual tener ese número de lápices que infinitos lápices.

Un saludo.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 43.724


Ver Perfil
« Respuesta #7 : 05/02/2019, 07:45:01 am »

Hola

 El problema es el mismo que se expone aquí, simplemente eligiendo el mismo coste para todos los objetos que tenemos y coste negativo para las longitudes que no tenemos.

https://www.geeksforgeeks.org/minimum-cost-to-fill-given-weight-in-a-bag/

 Por ejemplo si tenemos una mesa de longitud 100, lápices de longitud 12, bolígrafos de longitud 10, gomas de longitud 2 y afilalápices de longitud 1, la entrada del algortimo que se expone en el enlace sería:

 W=100, cost[]={1,1,-1,-1,-1,-1,-1,-1,-1,1,-1,1}

Saludos.
En línea
Zar@tuL
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 5


Ver Perfil
« Respuesta #8 : 06/02/2019, 04:18:56 pm »

Buenass,

@Luis Fuentes

Lo de anular el "factor" coste igualando su valor para todos los objetos creo que lo pillo :sonrisa: . A partir de ahí ya empiezo a perderme. (mi nivel de mates no es para ganar la Champions, sería para jugar en segunda división o peor).

Entiendo que hay un algoritmo que resuelve una matriz? Y que "insertamos" los datos conocidos en la matriz..... Y ya  :BangHead:

Te agradecería mucho que me lo explicaras y gracias por tu tiempo!!

Saludos.
En línea
Zar@tuL
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 5


Ver Perfil
« Respuesta #9 : 11/02/2019, 04:35:58 pm »

Hola y gracias a todos.

Teniendo ya la solución al problema (equiparándolo al mencionado "problema de la mochila") solo me queda aclararme en cuanto a la resolución (leyendo un poco de aquí y de allá), así que me doy por respondido.

Saludos y hasta la próxima.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!