Aproximado al Valor N=sumatorio de n valores de n tamaño

[ZaZ]

Hola, estoy intentando romperme un poco la cabecita y aunque tengo alguna
idea, solo una funcionaría al 100% pero dejando la balanza del lado de
chupar memoria en lugar de cpu :)
A ver, el problema es sencillo y se me plantea cuando kiero llenar un CD de
N tamaño (pongamos 700mb) con archivos, de una cantidad indetermidada pero
con un tamaño determinado. Es decir, tengo x archivos de diferentes tamaños
y quiero escoger, sin importancia de orden, la combinación de archivos que
más se aproxime a la cantidad deseada, en este caso 700. Si no me equivoco
eso seria un n! posibilidades siendo n el número de archivos siempre que el
sumatorio de ellos sea lo más próximo a 700, pero esta n también es variable
porqué kizás cabe uno como kizás 1000 o ninguno... Como ya véis,
matemáticamente no acabo de saber cuantas posibilidades se podrían dar. En
programación, y hablando en términos de C que tampoco domino mucho sólo he
encontrado una posibilidad. Se trataría de usar una estructura de tipo arbol
(metiendose de lleno con los punteros :( ) y así poder hacer todas las
posibilidades, hacer todos los sumatorios posibles y de todos los finales de
arbol obtener las sumas más aproximadas a 700 (aunque me daría n! resultados
por tenerme en cuenta el orden)...
En fin... no tengo ni prisa ni nada.. lo hago por amor al arte y pq me
gustaría realizar este programa (que no lo he visto hecho por ninguna parte)
pq sería útil para mi.
Alguna idea para este programador novato? ;)

ZaZ

[DrAcKe]

A mi me suena a problema de la mochila, con algunas variaciones.
Busca por ahí a ver si tu problema es ese exactamente.

By3z, DrAcKe

[ZaZ]

Gracias! he estado mirando y he encontrado esta web que está muy bien:
http://www.lsi.upc.es/~iea/transpas/4_dinamica/sld001.htm
aún estoy mirando pero creo que es exáctamente esto lo que buscaba... Si
tras estudiarlo veo que está bien y es lo k necesito, intentaré
implementarlo en C.

ZaZ

Post by DrAcKe
A mi me suena a problema de la mochila, con algunas variaciones.
Busca por ahí a ver si tu problema es ese exactamente.
By3z, DrAcKe

[Winfree]

Post by ZaZ
A ver, el problema es sencillo y se me plantea cuando kiero llenar un CD de
N tamaño (pongamos 700mb) con archivos, de una cantidad indetermidada pero
con un tamaño determinado. Es decir, tengo x archivos de diferentes tamaños
y quiero escoger, sin importancia de orden, la combinación de archivos que
más se aproxime a la cantidad deseada, en este caso 700.

Mirandolo así por encima creo que este es un problema típico del
simplex. La cuestión es que tu tienes una función objetivo, que es
maximizar el sumatorio de todos los ficheros, algo como

MAX f = SUM (tam_i * b_i)

donde tam_i es el tamaño del fichero i y b_i es la variable que tienes
que calcular, siendo en este caso un booleano, 0 si no se mete y 1 si
vas a meter el fichero i en el CD. Luego lo único que tienes que poner
es la restricción de que esa suma es menor que N, y ya con esto creo
que está todo.

La verdad es que tengo bastante oxidado esto del simplex, pero con
esto creo que ya puedes empezar a buscar por internet, para ver como
es el algoritmo este.

[ZaZ]

Ahora estaba comentando la respuesta de dracke que creo que es exactamente
lo que busco aunque aún tengo k leermelo todo. Sobre tu respuesta, creo que
es como una variable de lo que decía del arbol, ya que al fin y al cabo
haría falta un array grande para almacenar todos los sumatorios y encontrar
el más cercano a la cantidad. Antes de ir a dormir estube pensando en tu
opinión y también sería bastante correcto. Sobretodo por el tema del
booleano. Se podría imaginar como una tabla de verdad de n elementos (n
ficheros) y mediante tu fórmula, aplicada a cada linea de la tabla de la
verdad, validaría cuando hay un 1 y no lo sumaria cuando fuese un 0. Puesto
que hubiera n ficheros, necesitaría un array de 2^n para almacenar los
resultados. No es mala idea y si no me salgo con lo de la mochilita. Y ahora
pensando... suponiendo 20 archivos sería 2^n, k da un poco más de un
millon... y lo haría con un unsigned long int k son 32 bits, pasado a bytes
4, es decir, k necesitaría 4 meguitas de memoria para hacerlo con 20
archivos solo. En mi caso tampoco necesito mucho, pero si algun dia lo
kisiera hacer mayor me augmentaría los recursos encesarios de forma
exponencial y kizás no es del todo viable. En fin, ya intentaré ir
informando. Gracias

ZaZ

Post by Winfree

Post by ZaZ
A ver, el problema es sencillo y se me plantea cuando kiero llenar un CD de
N tamaño (pongamos 700mb) con archivos, de una cantidad indetermidada pero
con un tamaño determinado. Es decir, tengo x archivos de diferentes tamaños
y quiero escoger, sin importancia de orden, la combinación de archivos que
más se aproxime a la cantidad deseada, en este caso 700.

Mirandolo así por encima creo que este es un problema típico del
simplex. La cuestión es que tu tienes una función objetivo, que es
maximizar el sumatorio de todos los ficheros, algo como
MAX f = SUM (tam_i * b_i)
donde tam_i es el tamaño del fichero i y b_i es la variable que tienes
que calcular, siendo en este caso un booleano, 0 si no se mete y 1 si
vas a meter el fichero i en el CD. Luego lo único que tienes que poner
es la restricción de que esa suma es menor que N, y ya con esto creo
que está todo.
La verdad es que tengo bastante oxidado esto del simplex, pero con
esto creo que ya puedes empezar a buscar por internet, para ver como
es el algoritmo este.

[Winfree]

Post by ZaZ
Ahora estaba comentando la respuesta de dracke que creo que es exactamente
lo que busco aunque aún tengo k leermelo todo. ...
Antes de ir a dormir estube pensando en tu
opinión y también sería bastante correcto. Sobretodo por el tema del
booleano...

Es que en verdad mi propuesta y la de dracke son la misma, lo que pasa
es que yo te plantee el problema y el te dio el nombre con el que se
conoce el problema ;-)

Hace ya unos cuatro años tuve una asignatura que estaba dedicada a
estas cosas, y me acuerdo de algo del tema. La cuestión es que hay un
algoritmo, el del simplex, que sirve para calcular este tipo de
problemas. Habia una serie de variantes, pero es que ya no me acuerdo
muy bien, en cuatro años han muerto bastantes neuronas ;-) Basicamente
lo que haciamos nosotros para desarrollar el algoritmo a mano era
tener una tabla y operar en ella, aunque como ya te digo, no se si
programando el algoritmo habrá alguna forma de no tener que crear la
tabla entera.

[DrAcKe]

Totalmente deacuerdo con lo que dice Winfree
Yo a lo que me refiero es que el problema que buscas o eso me ha
parecido a mi es el problema de la mochila, otra cosa es el algoritmo
que uses para "resolverlo". Luego dependiendo de que variables
uses y de que tipo sean, y algunas cosas mas, puedes usar varios
algoritmos, entre ellos el simplex, como comentario decirte que hay
paquetes "solvers" que implementan esos algoritmos de resolución.

By3z, DrAcKe

[Bartomeu]

Hagas lo que hagas y como lo hagas, ten en cuenta que lo importante no es el
tamaño de los ficheros en el disco sino lo que ocuparán en el CD, es decir,
tendrás que tener en cuenta el tamaño del cluster del CD. Yo no sé cual es.

Yo tuve un problema similar hace mucho tiempo, copiando ficheros en
disquetes, y utilizaba el siguiente procedimiento, en pseudo código:
while (queden ficheros por copiar) {
if (hay algún fichero igual o menor del sitio disponible en el
CD)
Copiar el fichero más grande que quepa en el CD
else
Dar el CD por lleno y poner el siguiente CD
}

No conseguirás el mejor empaquetamiento, pero será bastante aceptable, si
los tamaños de los ficheros no son muy dispares.

Suerte.

[ZaZ]

Si, bueno, pero es esencial que consiga, dadas n! posibilidades, la mejor
para llegar a esa cantidad máxima. Llenar hasta cantidad y finalizar allí ya
puedo hacerlo manualmente pero desperdicio espacio. Sobre el cluster del CD,
también desconozco cuál es, pero bueno, solo se tiene k tener en cuenta si
copias un montón de archivos y tampoco es el caso. De momento lo hago de
forma manual y claro, como más pequeños són más facilidad para llegar a la
cantidad. Pero ahora imaginate por ejemplo, llenar un dvd con pelis, k todas
van entre 800 y 600mb y hay k llegar a 4,7gb. Si tienes unas 20 pelis
significan un montón de posibilidades, además de tener en cuenta k no te
caben todas... y manualmente, con estas cantidades te puedes acercar pero no
mucho y con suerte. En fin... k el programita tiene su utilidad para
muchisimas cosas :)

ZaZ

Post by Bartomeu
Hagas lo que hagas y como lo hagas, ten en cuenta que lo importante no es el
tamaño de los ficheros en el disco sino lo que ocuparán en el CD, es decir,
tendrás que tener en cuenta el tamaño del cluster del CD. Yo no sé cual es.
Yo tuve un problema similar hace mucho tiempo, copiando ficheros en
while (queden ficheros por copiar) {
if (hay algún fichero igual o menor del sitio disponible en el
CD)
Copiar el fichero más grande que quepa en el CD
else
Dar el CD por lleno y poner el siguiente CD
}
No conseguirás el mejor empaquetamiento, pero será bastante aceptable, si
los tamaños de los ficheros no son muy dispares.
Suerte.

[Bartomeu]

Post by ZaZ
Si, bueno, pero es esencial que consiga, dadas n! posibilidades, la
mejor para llegar a esa cantidad máxima. Llenar hasta cantidad y
finalizar allí ya puedo hacerlo manualmente pero desperdicio
espacio. Sobre el cluster del CD, también desconozco cuál es, pero
bueno, solo se tiene k tener en cuenta si copias un montón de
archivos y tampoco es el caso. De momento lo hago de forma manual y
claro, como más pequeños són más facilidad para llegar a la
cantidad. Pero ahora imaginate por ejemplo, llenar un dvd con pelis,
k todas van entre 800 y 600mb y hay k llegar a 4,7gb. Si tienes unas
20 pelis significan un montón de posibilidades, además de tener en
cuenta k no te caben todas... y manualmente, con estas cantidades te
puedes acercar pero no mucho y con suerte. En fin... k el programita
tiene su utilidad para muchisimas cosas :)

Siento insistir, el tamaño del cluster ES importante.

Puedes creer que has encontrado una combinación óptima para meter 7-8
películas en un DVD que no desperdicia ningún byte, y encontrate al
grabarlas que la última película no te cabe.
Insisto, debes trabajar con el tamaño que ocuparán los ficheros en el DVD,
no con el tamaño que tienen en el HD.
Incluso diría más. tendrías que investigar cuanto sitio te quitarán los
directorios.

Suerte.

[otroYo]

Es un caso que se soluciona de manera sencilla con un algoritmo voraz,
si dejas de lado la ordenación previa de los archivos por tamaño es de
complejidad N.

Ordenas los ficheros de mayor a menor en función de su tamaño. Luego
vas recorriendo los fichero de mayor a menor si entra en el tamaño
disponible lo metes (y restas al tamaño disponible el tamaño del
fichero). Si no pasas al siguiente. Así hasta que no quede espacio o
no queden ficheros.

La parte mas difícil es ordenar los ficheros.

Creo que es la forma mas eficiente. Pero no se, ya hace mucho ...

Post by ZaZ
Hola, estoy intentando romperme un poco la cabecita y aunque tengo alguna
idea, solo una funcionaría al 100% pero dejando la balanza del lado de
chupar memoria en lugar de cpu :)
A ver, el problema es sencillo y se me plantea cuando kiero llenar un CD de
N tamaño (pongamos 700mb) con archivos, de una cantidad indetermidada pero
con un tamaño determinado. Es decir, tengo x archivos de diferentes tamaños
y quiero escoger, sin importancia de orden, la combinación de archivos que
más se aproxime a la cantidad deseada, en este caso 700. Si no me equivoco
eso seria un n! posibilidades siendo n el número de archivos siempre que el
sumatorio de ellos sea lo más próximo a 700, pero esta n también es variable
porqué kizás cabe uno como kizás 1000 o ninguno... Como ya véis,
matemáticamente no acabo de saber cuantas posibilidades se podrían dar. En
programación, y hablando en términos de C que tampoco domino mucho sólo he
encontrado una posibilidad. Se trataría de usar una estructura de tipo arbol
(metiendose de lleno con los punteros :( ) y así poder hacer todas las
posibilidades, hacer todos los sumatorios posibles y de todos los finales de
arbol obtener las sumas más aproximadas a 700 (aunque me daría n! resultados
por tenerme en cuenta el orden)...
En fin... no tengo ni prisa ni nada.. lo hago por amor al arte y pq me
gustaría realizar este programa (que no lo he visto hecho por ninguna parte)
pq sería útil para mi.
Alguna idea para este programador novato? ;)
ZaZ

[Winfree]

Post by otroYo
Es un caso que se soluciona de manera sencilla con un algoritmo voraz,
si dejas de lado la ordenación previa de los archivos por tamaño es de
complejidad N.

Los algoritmos voraces son para encontrar soluciones rápidas, pero no
te aseguran la optimalidad, ya que una vez elegido un camino ya no se
lo vuelven a plantear. Y este caso que tu expones es claro que no es
así.

Post by otroYo
Ordenas los ficheros de mayor a menor en función de su tamaño. Luego
vas recorriendo los fichero de mayor a menor si entra en el tamaño
disponible lo metes (y restas al tamaño disponible el tamaño del
fichero). Si no pasas al siguiente. Así hasta que no quede espacio o
no queden ficheros.

Para demostrar que este algoritmo que propones no funciona, siempre y
cuando la cuestión sea poner el _máximo_ de ficheros, te pongo el
siguiente contra ejemplo. Imagínate la situación en la que tienes para
copiar 3 ficheros, uno de 3MB, y los otros dos de 2MB, y que la
capacidad donde se van a copiar es de 4MB, es decir, N = 4. Según tu
algoritmo se metería sólo un archivo de 3MB, cuando la solución óptima
sería meter los otros dos archivos de 2MB, ocupando por completo el
dispositivo.

Esta claro que el algoritmo voraz puede dar una solución aproximada,
pero si estás buscando el óptimo no van por ahí los tiros, yo sigo
pensando en el simplex ;-) Y como bien decia DrAcKe este problema es
similar al de la mochila, que se resuelve así, aunque no se si habia
una mejora para el simplex, es que ya no me acuerdo ;-)

[ZaZ]

merci por tu consejo pero te has olvidado de escoger los archivos, sin
importar el orden, que rellen al máximo el CD. Esa combinación no tiene pq
ser de menor a mayor, kizás con el último más los 3 primeros lo llena más k
los 4 primeros. Es allí donde radica el problema. Y tampoco haría falta un
programita, tan solo explorador de archivos, modo de vista detalles, orden
por tamaño y pillarlos. En fin, sigo pensando en ello, gracias.

ZaZ

Post by otroYo
Es un caso que se soluciona de manera sencilla con un algoritmo voraz,
si dejas de lado la ordenación previa de los archivos por tamaño es de
complejidad N.
Ordenas los ficheros de mayor a menor en función de su tamaño. Luego
vas recorriendo los fichero de mayor a menor si entra en el tamaño
disponible lo metes (y restas al tamaño disponible el tamaño del
fichero). Si no pasas al siguiente. Así hasta que no quede espacio o
no queden ficheros.
La parte mas difícil es ordenar los ficheros.
Creo que es la forma mas eficiente. Pero no se, ya hace mucho ...

Post by ZaZ
Hola, estoy intentando romperme un poco la cabecita y aunque tengo alguna
idea, solo una funcionaría al 100% pero dejando la balanza del lado de
chupar memoria en lugar de cpu :)
A ver, el problema es sencillo y se me plantea cuando kiero llenar un CD de
N tamaño (pongamos 700mb) con archivos, de una cantidad indetermidada pero
con un tamaño determinado. Es decir, tengo x archivos de diferentes tamaños
y quiero escoger, sin importancia de orden, la combinación de archivos que
más se aproxime a la cantidad deseada, en este caso 700. Si no me equivoco
eso seria un n! posibilidades siendo n el número de archivos siempre que el
sumatorio de ellos sea lo más próximo a 700, pero esta n también es variable
porqué kizás cabe uno como kizás 1000 o ninguno... Como ya véis,
matemáticamente no acabo de saber cuantas posibilidades se podrían dar. En
programación, y hablando en términos de C que tampoco domino mucho sólo he
encontrado una posibilidad. Se trataría de usar una estructura de tipo arbol
(metiendose de lleno con los punteros :( ) y así poder hacer todas las
posibilidades, hacer todos los sumatorios posibles y de todos los finales de
arbol obtener las sumas más aproximadas a 700 (aunque me daría n! resultados
por tenerme en cuenta el orden)...
En fin... no tengo ni prisa ni nada.. lo hago por amor al arte y pq me
gustaría realizar este programa (que no lo he visto hecho por ninguna parte)
pq sería útil para mi.
Alguna idea para este programador novato? ;)
ZaZ