[ Foro de Pascal ]

Todas las posibles combinaciones de un grupo de elementos

01-Oct-2011 11:09
Fulanito de Tal
15 Respuestas

¡Hola de nuevo! Estoy intentanto hacer un programa en pascal para optimizar el espacio en un dvd (o un cd) virgen. Introduzco como datos el número de archivos a grabar y el tamaño de cada archivo, también hay que introducir la capacidad máxima del soporte (cd = 700 Mb, dvd = 4,4 Gb). Luego el programa tiene que dar como resultado qué archivos grabo, para que se aproveche al máximo el espacio del dvd. Para ello el programa tiene que calcular todas las posibles combinaciones de los archivos. Primero tomándolos de uno en uno, luego de dos en dos, luego de tres en tres, etc. Para cada combinación suma los tamaños de los archivos que la componen y entonces comprueba si el tamaño total excede la capacidad del dvd o cd. En caso de que exceda rechaza esa combinación. Si no excede la compara con la combinación anteriormente seleccionada y almacenada en una variable, si es mayor el tamaño de la actual, queda la actual como la óptima. En caso de que el tamaño sea menor, la óptima es la anterior. Bueno, creo que se entiende lo que quiero decir¿no? :)
El problema que me encuentro es buscar la forma de ver todas las posibles combinaciones de un grupo de elementos. He buscado información en internet y he leído algo sobre algoritmos de Warshall, grafos y cosas así, por lo cual supongo que el tema no es fácil de resolver. Mi pregunta entonces es si realmente es complicado. Si lo fuese, entonces prefiero hacer una hoja de cálculo que aunque no es tan funcional, es más fácil de construir. Si fuese fácil, entonces me decantaría por programar en pascal porque es mucho más adaptable, sobre todo porque puedo introducir como dato el número de archivos a grabar (en la hoja de cáculo habría un máximo de archivos) ¿Alguno de vosotros lo intentó alguna vez? ¿Alguna idea de por dónde van los tiros? Gracias.


01-Oct-2011 12:10
Antonio P.G.

Hola,

Yo opino que el programa no sería muy largo, pero el algoritmo quizá un poco complejo. Además, si quieres hacerlo con memoria dinámica... puf.

Hombre, de esta forma, quiero decir, utilizando punteros, lo mejor es crear un TAD (Tipo abstracto de datos), para no tener que manejar directamente los punteros, puesto que eso puede ser un caos.

Si se va a utilizar memoria estática, ya se sabe; arrays de muchos campos.

Creo que la mejor estructura de datos para mantener los archivos (nombre y tamaño) en memoria, usando la estática, sería un array, claro.

Para hacer las combinaciones, podemos inventarnos un algoritmo 'parecido' (la verdad, no tan parecido) al de burbuja. En esto caso fijamos el primer archivo y lo combinamos con el 2º, 3º... Después fijamos el 2º y lo combinamos con el 3º, 4º... Esto para las combinaciones de dos. Para las de tres sería más complicado: fijamos la 1º y la 2º y combinamos con la 3º, 4º... y cuando hayamos hecho esto, fijamos la 1º con la 3º y combinamos con la 4º, 5º... Ahora que lo leo, suena a locura (¡qué de bucles! ¿No?).

Para almacenar las combinaciones supongo que se pueden usar varias estructuras. Quizás con un array de arrays... pero eso puede ser mucha memoria, porque el máximo número de combinaciones de 'n' elementos, tomados de diferentes cantidades... 'Stack overflow' seguro. Ja ja.

Tal vez la hoja de cálculo te lleve menos tiempo ;-). A ver qué dice el profe Nacho.

¡Ciao!


01-Oct-2011 12:46
Fulanito de Tal

Gracias por responder. Es que lo díficil es que el programa calcule todas las combinaciones, de dos en dos, de cuatro en cuatro, etc. Tal vez con una función recursiva.
En cuanto a almacenar las combinaciones, no es necesario. Sólo se almacena una, aquella cuyos elementos sumen el mayor tamaño posible sin pasarse de la capacidad del dvd. Si el tamaño de la combinación actual excede la capacidad del dvd, esa combinación se rechaza y no se almacena en ningún lugar. Si está dentro de la capacidad del dvd, esa combinación se compara con la anteriormente almacenada en un vector definido para tal propósito. Si es mayor el tamaño de la actual, la combinación actual se guarda y la anterior se borra. Si es mayor el tamaño de la anterior, permanece ésta y la actual se borra.
Sólo hay que definir dos vectores: uno donde se almacenan todos los archivos, es decir, el tamaño de cada uno. Y otro donde se va guardando la combinación de máximo tamaño sin que se pase de la capacidad del dvd.


01-Oct-2011 19:39
Nacho Cabanes (+83)

Ese problema que comentas (comentáis) es uno de esos problemas "que se estudian". Me refiero a que es una tipo de situación tan frecuente que ya existe una formulación de soluciones.

Es conocido como el "problema de la mochila", porque se suele plantear como una mochila (de capacidad limitada) en la que hay que poner ciertos objetos de ciertos valores a maximizar (o ciertos pesos), y no todos ellos caben, así que hay que escoger para conseguir llevar el conjunto de mayor valor posible.

Existen básicamente dos tipos de soluciones:

- Un algoritmo voraz (greedy method): vas tomando en cada momento la solución parcial más interesante, confiando en que un máximo local te lleve a un máximo global. Es un algoritmo fácil de plantear y rápido de resolver, pero en muchos problemas reales no lleva a la solución óptima, aunque a veces sí a una "suficientemente buena".

- Un algoritmo de búsqueda en profundidad (backtracking), que prueba todas las soluciones posibles. Se suele plantear como un algoritmo recursivo, que a partir de cada posibilidad con un elemento va probando todas las de 2 elementos a las que conduzca, y de ésta a todas las de 3, etc. Tienen un coste enorme, tanto en tiempo como en espacio ocupado (memoria), por lo que se suele intentar optimizar, descartando las soluciones que claramente no van a producir ninguna mejora (ramificación y poda, branch & bound).

Tienes más detalles en el artículo de la Wikipedia en español (que no me gusta demasiado, porque da pocas respuestas concretas):

http://es.wikipedia.org/wiki/Problema_de_la_mochila

o bien en inglés (más formal, aun así poco práctico, pero con enlaces interesantes):

http://en.wikipedia.org/wiki/Knapsack_problem

Entre los enlaces está este, por ejemplo, que es en Javascript, interactivo:

http://allievi.sssup.it/jacopo/BB/

y, en cualquier caso, con esas palabras clave seguro que encuentras más de un artículo interesante que te pueda ayudar.  ¡Suerte!


01-Oct-2011 21:16
Fulanito de Tal

Gracias. Voy a investigar algo sobre el problema de la mochila. Si tal me quedo con la hoja de cálculo.


09-Oct-2011 23:20
Fulanito de Tal

Hola de nuevo. Por fin he escrito el programilla. Me ha dado algo de lata pero menos de lo que pensaba.
Estuve buscando ideas por internet pero no encontré ninguna que me convenciese y al final lo tuve que hacer yo solito.
Me gustaría adjuntar una copia pero ocupa más de 12 Kb, cuando el máximo permitido en la web es de 10. Si alguien quiere el programa para probarlo que me lo pida por email.

Cuando se inicia el programa éste pregunta por la capacidad del dispositivo. Hay que introducir el dato en Gigabytes.
Si es un CD, normalmente de 700 Mb, antes hay que convertir los Megas en Gygas dividiendo por 1024.
Luego pregunta el número de archivos a grabar. Máximo 29. A partir de 24 hay que esperar unos 4 segundos, pues son muchas las combinaciones a calcular. Para 29 archivos el tiempo que tarda son más de dos minutos, para mi procesador. Otros tal vez más o menos. Si el número de archivos es 20 o menos entonces es casi instantáneo.
Luego nos pide que vayamos introduciendo el tamaño de cada archivo en Mb.
Si alguno de ellos está en Gb antes de teclearlo hay que pasarlo a Mb multiplicando por 1024.

Entonces el programa nos da la combinación de archivos que ocupa el máximo espacio posible sin sobrepasar la capacidad del dispositivo. Es una lista de los archivos seleccionados por el programa. Como no se han introducido nombres, la lista consiste en los tamaños de los archivos. A mí al principio me parecía algo soso, pero luego pensé que es mejor así que estar tecleando uno por uno los nombres de los archivos.
A continuación ofrece un resumen del estado en que quedará el DVD o el CD después de grabarse:
La capacidad del mismo, es un dato que ya se conocía al principio.
El espacio que ocuparán los archivos cuando se graben, en Gb.
Y el espacio libre que quedará en el dispositivo, en Mb.

El programa funciona muy bien, estoy contento con él, incluso yo diría que funciona demasiado bien. Es que si son muchos archivos, como por ejemplo 10 o más, ajusta tanto el espacio que casi siempre sobran en el dvd menos de 10 megas. Y aquí aparece un problema, es que muchos archivos tienen un decimal en el tamaño, por ejemplo 656,7 Mb, por lo cual supongo que será un redondeo, que el tamaño real no es ese. Así que aunque el programa diga que sobran unos megas, al ir a grabar resulta que no hay espacio, que faltan en vez de sobrar. La solución:
volver a correr el programa y cuando pregunte la capacidad del dispositivo en vez de poner 4,4, la normal en un DVD, pondremos 4.39 o incluso 4.38. Para un CD haremos lo mismo si no hay espacio.

Voy a describir un poco como está escrito:
Los tamaños de los archivos los guarda en un vector. Y luego hace todas las combinaciones posibles entre los elementos del vector, primero de uno en uno, luego de dos en dos, etc. Bueno, en realidad no trabaja directamente con el vector de archivos, sino con un vector de índices porque es más fácil de manejar. Luego, para cada combinación, suma el tamaño de los archivos que la componen. Si ese tamaño sobrepasa la capacidad del dispositivo, esa combinación se rechaza. Si no la sobrepasa, entonces esa combinación es candidata a ser óptima: se compara con la combinación óptima anterior y si la actual tiene mayor tamaño queda como óptima la actual, descartándose la anterior. De lo contrario, queda la anterior como óptima. Al final del proceso la combinación seleccionada es la de mayor tamaño posible.

El intríngulis de todo esto es conseguir todas las combinaciones posibles. Al final no fue tan difícil. A grosso modo se hace lo siguiente: se utilizan tres bucles anidados. El más externo va desde 1 hasta el número de archivos a grabar. Este bucle nos dice si vamos a seleccionar los archivos de 1 en 1, de 2 en 2, etc. Inmediatamente se calcula el número de combinaciones para esos archivos seleccionados.
Luego se entra en otro bucle que va desde 1 hasta el número de combinaciones calculado anteriormente.
Y a continuación se entra en el bucle más interno, donde se obtiene el índice que se pondrá en cada posición de la combinación actual. Es un bucle inverso que va desde la posición mayor a la menor, porque es la posición más externa la que más rápido va cambiando. Un ejemplo de combinaciones de diez elementos tomados de tres en tres sería: 1-2-3, 1-2-4, 1-2-5, 1-2-6, etc.
Como se ve, es el número que está en la posición tres la que avanza en cada combinación nueva. Los números en las otras posiciones sólo avanzan si el número de la posición inmediatamente superior llegó al máximo. Por ejemplo al llegar a la combinación 1-2-10, la segunda posición es la que avanza un lugar, pues la tercera ha llegado al máximo.
Y aquí hay otro problema porque el número máximo depende de la posición. Si tenemos 10 archivos y los estamos tomando de tres en tres, la última combinación, formada por los máximos de cada posición, será: 8-9-10. Si son 7 archivos y los estamos tomando de 4 en 4, la última combinación será 4-5-6-7.
Por consiguiente en este bucle más interno, lo primero que se hace es calcular el número máximo para cada posición.
Todavía hay más cosas. Cuando un número de una posición (excepto la última) avanza un lugar, las posiciones posteriores tienen que "reiniciarse", no a 0 ni a 1, sino al número inmediatamente superior al de la combinación anterior. Ejemplo: si estamos en la combinación 1-9-10, las dos últimas posiciones han llegado a sus respectivos máximos. Entonces la primera pasa de 1 a 2. Y luego las otras dos tienen que reiniciarse a 3 y 4. Por tanto la combinación siguiente a 1-9-10 es la 2-3-4.
Bueno, no digo nada más, ya he soltado mucho rollo. El código está muy comentado porque es algo que me parece tan complejo que si un día vuelvo a él me va a costar entenderlo. Por eso puse tantos comentarios. Creo que se entederán bien si alguien quiere leerlos. Si de todas formas hay alguna duda, me la preguntáis. Y sí puedo la respondo.
Un saludo, muchas gracias por vuestra ayuda.


09-Oct-2011 23:46
Fulanito de Tal

En el anterior comentario he tenido un despiste: Casi al final, donde dice:
Todavía hay más cosas. Cuando un número de una posición (excepto la última) avanza un lugar, las posiciones posteriores tienen que "reiniciarse", no a 0 ni a 1, sino al número inmediatamente superior al de la combinación anterior.
En realidad debería decir:
Todavía hay más cosas. Cuando un número de una posición (excepto la última) avanza un lugar, las posiciones posteriores tienen que "reiniciarse", no a 0 ni a 1, sino al número inmediatamente superior al de la POSICIÓN anterior.


10-Oct-2011 21:50
Nacho Cabanes (+83)

Pues yo lo veo interesante, sí podrías compartir el fuente. En vez de adjuntarlo, copia y pega y así se podrá leer directamente en el foro (si reemplazas antes las tabulaciones por espacios, se podrá leer conservando el sangrado incluso).

Por lo que leo, no llegaste a hacerlo con llamadas recursivas, ¿no?


10-Oct-2011 23:27
Fulanito de Tal

Pues akí teneis el código por si a alguien le interesa. He incluído todos los comentarios, tal como los dejé para mí. Puede que para alguien le resulte pesado porque son muchos.
El programa seguro que tiene muchas ineficiencias. Después de escribirlo me di cuenta de por lo menos una: en varias ocasiones utilicé if begin... despues de un else, en lugar de usar else if directamente. Es la costumbre de no usar nunca else if. No me atreví a cambiarlo porque igual metía la pata y tenía que volver a
reconstruir los if. Así que lo dejé estar como está. Si no tarda ni un segundo en calcular todas las combinaciones para 20 archivos, a mí me parece que está perfecto así. Cubre de sobra mis necesidades.
No utilicé funciones recursivas. Sólo hice un par de programas con ellas. Uno fue para calcular la sucesión de Fibonacci. Me acuerdo que hice las dos versiones, con recursividad y con un bucle normal. Con el bucle normal tarda menos de un segundo en calcular el elemento 100 de la sucesión. Con recursividad al llegar al 40 y pocos se tira un montón de tiempo para calcular el siguiente. Así que decidí no usar nunca más recursividad a no ser que no haya otra forma de programar un problema concreto.
Bueno, pues akí está el código:

program
 optimizador_dvds_cds;

{Programa para optimizar el espacio vacío en un DVD o un CD virgen.
Escrito durante los días 7, 8 y 9 de octubre de 2011.
Comprobado con Free Pascal Compiler 2.4.0-2,
en Linux 2.6.32-5-amd64; Debian squeeze 6.0.3}

uses
 crt;

var
 numero_archivos: byte;
 posicion_avance, posicion_maximo: byte;
 maximo: byte;
 combinaciones: longint;
 bucle_auxiliar: longint;
 bucle_archivos_tomados, bucle_combinaciones, bucle_posiciones: byte;
 vector_completo, vector_optimo: array of real;
 vector_indices: array of byte;
 suma_actual, suma_optima, capacidad: real;

{La funcion_factorial y la funcion_combinaciones calculan las combinaciones
de n archivos, tomados de m en m. No se calcula todo el factorial
7 x 6 x 5 x 4 x 3 x 2 x 1, porque como hay factoriales tanto en el
numerador como en el denominador, puede simplificarse la división.
De esta manera se ahorran iteraciones en el bucle y se pueden calcular
combinaciones de números más grandes, pues no se rebasa tan fácilmente
el máximo permitido para el tipo de dato definido.
Ejemplo para calcular el número de combinaciones de 7 elementos
tomados de 3 en 3:
Numerador: 7 x 6 x 5 x 4 x 3 x 2 x 1 (es decir: 7!)
Denominador: 3 x 2 x 1 x 4 x 3 x 2 x 1 (es decir: 3! x (7 - 3)!)
Despues de simplificar, la cosa va a quedar así:
Numerador: 7 x 6 x 5
Denominador: 3 x 2 x 1
Cómo trabaja la funcion_combinaciones:
Compara m con (n - m). El mayor se almacena en la variable "mayor", y el
menor en la variable "menor". Luego se hace un llamamiento a la
funcion_factorial, especificando en el numerador un bucle desde
("mayor" + 1) hasta n. Y en el denominador un bucle desde 1 hasta "menor"
La funcion_factorial es más sencilla, simplemente calcula un producto
acumulado dentro de un bucle cuyo principio y final son determinados
por funcion_combinaciones.}

function funcion_factorial (a, b: byte): qword;
var
 producto: qword;
 bucle: byte;
begin
 producto:= 1;
 for bucle:= a to b do
 begin
   producto:= producto * bucle;
 end;
 funcion_factorial:= producto;
end;

function funcion_combinaciones (n, m: byte): longint;
var
 mayor, menor: byte;
 numerador, denominador: qword;
begin
 if m > (n - m) then
 begin
   mayor:= m;
   menor:= n - m;
 end
 else
 begin
   mayor:= n - m;
   menor:= m;
 end;
 numerador:= funcion_factorial (mayor + 1, n);
 denominador:= funcion_factorial (1, menor);
 funcion_combinaciones:= numerador div denominador;
end;

////////////////////Empieza el programa/////////////////////

begin
 clrscr;

 writeln ('OPTIMIZADOR DE GRABACIONES');
 writeln ('==========================');

 writeln;

 writeln ('Introducción de datos');
 writeln ('---------------------');

 write ('Capacidad del dispositivo (en Gb): ');
 readln (capacidad);

 write ('Numero de archivos a grabar (maximo 29): ');
 readln (numero_archivos);

 {Dimensionamos vector_completo. En este vector se almacenan los tamaños
 en Mb de todos los archivos.}

 setlength (vector_completo, numero_archivos);

 writeln ('Tamano de cada archivo (en Mb):');

 {En este bucle_auxiliar se van a leer los tamaños de cada archivo.
 Los índices del vector_completo restan 1 al bucle_auxiliar
 porque como fue dimensionado mediante setlength, los elementos
 del vector empiezan a numerarse en 0, no en 1. Esto mismo va a
 pasar con los otros dos vectores que tenemos definidos, pues todos se
 dimensionan con setlength.}
 {El bucle_auxiliar se usa en diferentes partes del programa cuando
 sea necesario un bucle para una cuestión secundaria.}

 for bucle_auxiliar:= 1 to numero_archivos do
 begin
   write ('   Archivo ', bucle_auxiliar,': ');
   readln (vector_completo [bucle_auxiliar-1]);
 end;

 {suma_actual almacena el tamaño total de los archivos que estamos
 considerando en la combinación actual.
 suma_optima almacena el tamaño total de la combinación óptima
 almacenada hasta ese momento. Se entiende por combinación óptima
 aquella cuyos archivos suman el mayor tamaño pero sin alcanzar
 la capacidad del dispositivo.}

 suma_actual:= 0; suma_optima:= 0;

 {El bucle "bucle_archivos_tomados" indica el número de archivos que se
 tienen en cuenta cada vez: de 1 en 1, de 2 en 2, de 3 en 3, etc.}

 for bucle_archivos_tomados:= 1 to numero_archivos do
 begin

   {Se dimensionan los vectores según cuantos archivos tengamos en cuenta.
   El vector_indices almacena los índices del vector_completo que se
   están considerando en cada combinación. Prácticamente todas las
   operaciones se hacen con el vector_índices porque es más fácil de manejar.
   Al final, para calcular suma_actual, se busca en el vector_completo
   el archivo correspondiente indicado por el vector_indices.
   El vector_optimo, almacena la combinación óptima hasta ese momento}

   setlength (vector_indices, bucle_archivos_tomados);
   setlength (vector_optimo, bucle_archivos_tomados);

   {Se calcula el número de combinaciones para ese número de archivos
   seleccionados (combinaciones de n archivos tomados de m en m)}

   combinaciones:= funcion_combinaciones (numero_archivos, bucle_archivos_tomados);

   {El "bucle_combinaciones" recorre todas las combinaciones posibles dado
   el número de archivos seleccionados en el bucle anterior}

   for bucle_combinaciones:= 1 to combinaciones do
   begin
     if bucle_combinaciones = 1 then //La primera combinación
     begin

       {La primera combinación tiene un tratamento especial porque
       siempre es la sucesión de los números naturales. Por ejemplo, si
       estamos seleccionando 3 archivos, la primera combinación es
       1-2-3. Si estamos seleccionando 5 archivos la primera
       combinación sería 1-2-3-4-5. Más abajo se amplía esta
       expliación un poco más.}

       for bucle_auxiliar:= 1 to bucle_archivos_tomados do
       begin
         vector_indices [bucle_auxiliar-1]:= bucle_auxiliar;
       end;

     end //if la primera combinación

     else //las demás combinaciones
     begin

       {Las variables posicion_avance y posicion_maximo almacenan la
       posición que avanza o que llega al máximo. Ejemplo: si tenemos
       un total de 15 archivos y estamos actualmente en la combinación
       2-7-15, entonces posicion_maximo = 3, ya que es la tercera
       posición la que llegó al máximo. La siguiente combinación
       será 2-8-9, por tanto posicion_avance = 2, pues la segunda
       posición es la que avanzó un lugar, pasando de 7 a 8}

       posicion_avance:= 0; posicion_maximo:= 0;

       {Este bucle_posiciones recorre todas las posiciones de cada
       combinación. Empieza por la última porque es la que va
       cambiando en cada combinación}

       for bucle_posiciones:= bucle_archivos_tomados downto 1 do
       begin

         {Cálculo del máximo que se puede alcanzar en cada posición:
         Como estamos haciendo combinaciones, no permutaciones, resulta
         indiferente la combinación 1-2-3 que la 2-3-1. Además no
         se pueden repetir elementos en cada combinación: sería absurdo
         grabar el mismo archivo más de una vez en un DVD. Si tenemos en
         cuenta estas dos cosas, para todas las combinaciones, cada
         posición tendrá como mínimo el valor de la anterior + 1. Nunca
         podría existir esta combinación: 3-5-2-9. En la posición
         segunda hay un 5, por tanto en la tercera no puede haber un
         2, como mínimo terdrá que haber un 6, porque dicha combinación
         ya fue vista anteriormente: 3-5-2-9 es lo mismo que 2-3-5-9.
         Si continuamos con este razonamiento veremos que la última
         combinación es siempre una sucesión de números naturales
         que termina con el número maximo de archivos. Por ejemplo, si son
         10 los archivos y los estamos tomando de 3 en 3, la última
         combinación será 8-9-10. Si los archivos fuesen 17 y los estamos
         tomando de 4 en 4, la última combinación será 14-15-16-17.
         Por tanto la fórmula para calcular el número máximo en cada
         posición depende del número total de archivos, de cuantos
         estemos tomando en este momento y de la posición actual.}

         maximo:= numero_archivos - (bucle_archivos_tomados - bucle_posiciones);

         {Si llegamos al máximo posible en una posición, se almacéna
         esa posición en la variable posicion_maximo}

         if vector_indices [bucle_posiciones-1] = maximo then
         begin
           posicion_maximo:= bucle_posiciones;
         end

         else //El elemento de la posicion actual no es el máximo posible
         begin

           {La última posición de cada combinación tiene un tratamiento
           especial, pues SIEMPRE avanza un número.
           Por ejemplo si estamos en la combinación 1-3-5-8-9, la última
           posición avanza de 9 a 10 (siempre y cuando no se haya llegado antes
           al máximo, cosa imposible porque estamos dentro del "else".)
           En este if lo que se hace es avanzar un número la última
           posición}

           if bucle_posiciones = bucle_archivos_tomados then
           begin
             vector_indices [bucle_posiciones-1]:= vector_indices [bucle_posiciones-1] + 1;
           end

           else //Si la posición actual no es la última
           begin

             {Las demás posiciones que no son la última avanzan
             un número sólo si la posición posterior llegó al maximo.
             Ejemplo: combinación actual: 3-4-10. Si el número de archivos
             es 10, la tercera posición llegó al maximo, luego la segunda
             pasa de 4 a 5.}

             if posicion_maximo = (bucle_posiciones + 1) then
             begin
               vector_indices [bucle_posiciones-1]:= vector_indices [bucle_posiciones-1] + 1;

               {También hay que anotar que la posición actual avanzó
               un número (más adelante veremos porqué se anota)}

               posicion_avance:= bucle_posiciones;
             end; //else if posicion_maximo

           end; //else no estamos en la última posicion

         end; //else no estamos en el valor maximo de la posición actual

       end; //for bucle_posiciones

     end; //else combinación siguiente a la primera

     {Cuando una posición cualquiera, excepto la última, avanza un
     lugar, todas las posteriores tienen que "reiniciarse", pero no a 0,
     sinó al valor que tenga la respectiva anterior + 1. Supongamos que
     estamos con la numeración decimal, y llegamos al número 199.
     Entonces la primera posición avanza un lugar, pues las posteriores
     llegaron al máximo. La primera posición pasa de 1 a 2. Entonces
     todas las posiciones posteriores se reinician a 0, quedando por
     tanto el número 200.
     Las combinaciones tienen las características que más atrás comentamos,
     si estuviésemos por ejemplo en la combinación 2-5-9-10 (suponiendo 10
     archivos), la segunda posición tendrá que pasar de 5 a 6, pues las
     dos posiciones posteriores llegaron a los respectivos máximos. Pero
     la nueva combinación es 2-6-7-8, no es 2-6-1-1, ni 2-6-0-0.
     Ahora vamos a "reiniciar" todas las posiciones posteriores a la que
     avanzó un lugar.}

     if posicion_avance <> 0 then
     begin
       for bucle_auxiliar:= (posicion_avance + 1) to bucle_archivos_tomados do
       begin
         vector_indices [bucle_auxiliar-1]:= vector_indices [bucle_auxiliar-2] + 1;
       end;
     end;

     {Aquí comienza la suma de los tamaños de los archivos de la combinación actual}

     for bucle_auxiliar:= 1 to bucle_archivos_tomados do
     begin
       suma_actual:= suma_actual + vector_completo [vector_indices [bucle_auxiliar-1]-1];
     end;

     suma_actual:= suma_actual / 1024; //porque 1 Gb = 1024 Mb.
                                       //Los archivos están en Mb y el
                                       //dispositivo en Gb

     {Comienza el almacenamento en el vector_optimo. Para almacenar una
     combinación, ésta tiene que cumplir dos requisitos: ser de menor
     tamaño que la capacidad del dispositivo, y ser de mayor tamaño
     que la combinación anteriormente almacenada. Así, cuando lleguemos al
     final del proceso y fueron examinadas todas las combinaciones,
     la combinación almacenada será la de mayor tamaño posible.
     Antes de almacenar la combinación en vector_optimo hay que buscar
     el tamaño de esos archivos en el vector_completo. El archivo
     buscado estará en la posición que indique el vector_indices}

     if (suma_actual < capacidad) and (suma_actual > suma_optima) then
     begin
       for bucle_auxiliar:= 1 to bucle_archivos_tomados do
       begin
         vector_optimo [bucle_auxiliar-1]:= vector_completo [vector_indices [bucle_auxiliar-1]-1];
       end;
       suma_optima:= suma_actual;
     end; // fin almacenamento

     suma_actual:= 0;

   end; // bucle_combinaciones

 end; // bucle_archivos_tomados

 {Comienza la presentación de los resultados.}

 clrscr;

 writeln ('OPTIMIZADOR DE GRABACIONES');
 writeln ('==========================');

 writeln;

 writeln ('Archivos seleccionados');
 writeln ('----------------------');

 for bucle_auxiliar:= 1 to numero_archivos do
 begin
   if vector_optimo [bucle_auxiliar-1] <> 0 then
   begin
     writeln (vector_optimo [bucle_auxiliar-1]:0:4);
   end;
 end;

 writeln;

 writeln ('Situacion en el dispositivo de almacenamiento');
 writeln ('---------------------------------------------');

 writeln ('Capacidad: ', capacidad:0:4,' Gb');

 writeln ('Espacio ocupado: ', suma_optima:0:4,' Gb');

 writeln ('Espacio desperdiciado: ', (capacidad - suma_optima) * 1024 :0:4,' Mb');

 writeln;

end.


10-Oct-2011 23:58
Fulanito de Tal

Pues he copiado el código tal como está aquí y no compila. El compilador dice que hay un carácter ilegal en la línea 2. Supongo que se referirá al espacio. No entiendo por qué, a no ser que se deba a que cambié los tabuladores por espacios en Geany en vez de usar un procesador de textos normal.
Si a vosotros tampoco os compila podría intentar pegar el código con tabuladores, a ver si así va.


13-Oct-2011 18:20
Fulanito de Tal

Pego el fuente sin comentarios y con tabuladores a ver si ahora compila


{$codepage UTF8}

program
optimizador_dvds_cds;

uses
crt;

var
numero_archivos: byte;
posicion_avance, posicion_maximo: byte;
maximo: byte;
combinaciones: longint;
bucle_auxiliar: longint;
bucle_archivos_tomados, bucle_combinaciones, bucle_posiciones: byte;
vector_completo, vector_optimo: array of real;
vector_indices: array of byte;
suma_actual, suma_optima, capacidad: real;

function funcion_factorial (a, b: byte): qword;
var
producto: qword;
bucle: byte;
begin
producto:= 1;
for bucle:= a to b do
begin
producto:= producto * bucle;
end;
funcion_factorial:= producto;
end;

function funcion_combinaciones (n, m: byte): longint;
var
mayor, menor: byte;
numerador, denominador: qword;
begin
if m > (n - m) then
begin
mayor:= m;
menor:= n - m;
end
else
begin
mayor:= n - m;
menor:= m;
end;
numerador:= funcion_factorial (mayor + 1, n);
denominador:= funcion_factorial (1, menor);
funcion_combinaciones:= numerador div denominador;
end;

////////////////////////////////////////////////////////////
////////////////////Empieza el programa/////////////////////
////////////////////////////////////////////////////////////

begin
clrscr;

writeln ('OPTIMIZADOR DE GRABACIONES');
writeln ('==========================');

writeln;

writeln ('Introducción de datos');
writeln ('---------------------');

write ('Capacidad del dispositivo (en Gb): ');
readln (capacidad);

write ('Número de archivos a grabar (maximo 29): ');
readln (numero_archivos);

setlength (vector_completo, numero_archivos);

writeln ('Tamano de cada archivo (en Mb):');

for bucle_auxiliar:= 1 to numero_archivos do
begin
write ('   Archivo ', bucle_auxiliar,': ');
readln (vector_completo [bucle_auxiliar-1]);
end;

suma_actual:= 0; suma_optima:= 0;

for bucle_archivos_tomados:= 1 to numero_archivos do
begin
setlength (vector_indices, bucle_archivos_tomados);
setlength (vector_optimo, bucle_archivos_tomados);
combinaciones:= funcion_combinaciones (numero_archivos, bucle_archivos_tomados);

for bucle_combinaciones:= 1 to combinaciones do
begin
if bucle_combinaciones = 1 then
begin
for bucle_auxiliar:= 1 to bucle_archivos_tomados do
begin
vector_indices [bucle_auxiliar-1]:= bucle_auxiliar;
end;

end

else
begin
posicion_avance:= 0; posicion_maximo:= 0;
for bucle_posiciones:= bucle_archivos_tomados downto 1 do
begin
maximo:= numero_archivos - (bucle_archivos_tomados - bucle_posiciones);
if vector_indices [bucle_posiciones-1] = maximo then
begin
posicion_maximo:= bucle_posiciones;
end

else
begin
if bucle_posiciones = bucle_archivos_tomados then
begin
vector_indices [bucle_posiciones-1]:= vector_indices [bucle_posiciones-1] + 1;
end

else
begin
if posicion_maximo = (bucle_posiciones + 1) then
begin
vector_indices [bucle_posiciones-1]:= vector_indices [bucle_posiciones-1] + 1;
posicion_avance:= bucle_posiciones;
end;
end;
end;
end;
end;

if posicion_avance <> 0 then
begin
for bucle_auxiliar:= (posicion_avance + 1) to bucle_archivos_tomados do
begin
vector_indices [bucle_auxiliar-1]:= vector_indices [bucle_auxiliar-2] + 1;
end;
end;

for bucle_auxiliar:= 1 to bucle_archivos_tomados do
begin
suma_actual:= suma_actual + vector_completo [vector_indices [bucle_auxiliar-1]-1];
end;

suma_actual:= suma_actual / 1024;

if (suma_actual < capacidad) and (suma_actual > suma_optima) then
begin
for bucle_auxiliar:= 1 to bucle_archivos_tomados do
begin
vector_optimo [bucle_auxiliar-1]:= vector_completo [vector_indices [bucle_auxiliar-1]-1];
end;
suma_optima:= suma_actual;
end;

suma_actual:= 0;

end;

end;

clrscr;

writeln ('OPTIMIZADOR DE GRABACIONES');
writeln ('==========================');

writeln;

writeln ('Archivos seleccionados');
writeln ('----------------------');

for bucle_auxiliar:= 1 to numero_archivos do
begin
if vector_optimo [bucle_auxiliar-1] <> 0 then
begin
writeln (vector_optimo [bucle_auxiliar-1]:0:4);
end;
end;

writeln;

writeln ('Situación en el dispositivo de almacenamiento');
writeln ('---------------------------------------------');

writeln ('Capacidad: ', capacidad:0:4,' Gb');

writeln ('Espacio ocupado: ', suma_optima:0:4,' Gb');

writeln ('Espacio desperdiciado: ', (capacidad - suma_optima) * 1024 :0:4,' Mb');

writeln;

end.




Pues ahora sí que compila. Y funciona perfectamente. Un saludo.


18-Dec-2011 10:45
Fulanito de Tal

Hola de nuevo. El programa tiene un fallo. La verdad es que ya hace tiempo que lo sé pero hasta ayer no me puse a buscarlo.
Desde que empecé a utilizarlo, el programa hacía cosas que no debería. Una de ellas es que si se cambia el orden en que se introducen los tamaños de los archivos a grabar entonces el resultado es diferente. Lo cual es completamente ilógico pues si se busca la combinación de archivos con el mayor tamaño posible, da igual el orden en que se introduzcan. También tenía otro comportamiento extraño similar. Si ejecuto el programa con N archivos, y luego vuelvo a ejecutarlo con los mismos archivos pero añadiendo otro más, entonces a veces me daba un resultado peor, cuando debería dar como mínimo un resultado igual, y en muchos casos debería ser mejor.
Pues ayer me puse a buscar el fallo, y éste se encuentra en la declaración de variables:
Hay una línea que dice así: bucle_archivos_tomados, bucle_combinaciones, bucle_posiciones: byte;
Y dos líneas más arriba dice: combinaciones: longint;
El bucle_combinaciones va desde 1 hasta combinaciones. Está claro que si combinaciones es una variable longint, bucle_combinaciones al ser byte no va a poder alcanzar todas las combinaciones posibles cuando éstas son más de 255.
Cuando bucle_combinaciones llega a 255, el siguiente paso es empezar de nuevo desde 1. Por tanto, si hay más de 255, las demás combinaciones quedan sin ser analizadas.
Por eso el resultado era diferente si cambiaba el orden de los datos. Si una de las combinaciones que quedaba sin analizar era, por ejemplo, la 3-8-11, entonces no da lo mismo que en esas tres posiciones estén unos archivos que otros, pues el resultado va a ser diferente. Algo parecido pasa cuando se introduce un archivo más.
Para que funcione bien hay que cambiar el tipo de variable de bucle_combinaciones y dejarlo como longint.
También hice algunas mejoras en el programa, como dar la opción de teclear los datos o leerlos desde un fichero, permitir cambiar la capacidad del dvd o cd sin tener que volver a leer todos los datos, poder cambiar un dato si fue mal tecleado sin necesidad de reiniciar el programa.
Un saludo.


23-Dec-2011 11:14
Nacho Cabanes (+83)

Hola, Fulanito!  ;-)

Como dices, lo de que el límite para las combinaciones fuera un byte suena a demasiado restrictivo para un caso real en el que haya más de 5 ficheros.

Veo que las demás mejoras son de usabilidad, no de funcionalidad, pero también vendrán bien, al hacerlo más amigable.

Si quieres compartir el resultado con nosotros, por si alguien puede sugerir algo o bien le resulta útil, sabes que será bienvenido. Yo, como siempre, no puedo comprometerme con que lo vaya a poder analizar con detenimiento, porque no ando muy sobrado de tiempo, aunque eso en vacaciones suele cambiar... pero poco.  ;-)


29-Dec-2011 20:54
Fulanito de Tal

Hola. Dejo el código con las nuevas modificaciones.
Entre ellas está la posibilidad de leer los datos de un fichero o teclearlos a mano. Si se elige leer los datos de un fichero, éste ha de llamarse "datos_archivos_grabacion" (sin extensión) y ha de estar en el mismo directorio donde se encuentre el programa compilado. Si se quiere otro nombre u otro directorio hay que cambiar la línea de código donde se asigna el fichero a la variable 'datos_archivos'. También se puede modificar el código para que pregunte el directorio y el nombre del archivo. Pero yo no lo hice porque no me apetecía que el programa me estuviese preguntando la dirección y el nombre cada vez que lo ejecuto, porque siempre utilizo el mismo fichero que está siempre en la misma carpeta, así que me pareció perder el tiempo y dejé el código tal como está.
Otro asunto importante. El fichero ha de ser de texto y con un dato en cada línea. En la primera línea se pondrá la capacidad del dispositivo (en Gb), y en las demás el tamaño de cada fichero. De nuevo, como el programa es para mí lo hice ajustado a como yo trabajo.
Otras modificaciones:
Permite cambiar el tamaño de un archivo por si se tecleó mal. Así se evita tener que ejecutar el programa desde el principio si se comete un error. Es muy engorroso volver a teclear de nuevo todos los datos.
Se permite cambiar la capacidad del dvd o cd al final. Esto es porque el tamaño de los archivos que aparece en el explorador de archivos es una aproximación. El tamaño real es algo mayor. Y como en muchos casos el programa aprovecha casi al máximo la capacidad del dvd uno se encuentra con la sorpresa de que los ficheros seleccionados no caben. En este caso antes había que volver a iniciar el programa cambiando la capacidad, y además volver a escribir todo a mano. Ahora se introduce la nueva capacidad y el programa calcula una nueva combinación. La nueva capacidad que teclearemos pasará de ser (en un dvd) de 4.4 a 4.39. Si los ficheros siguen sin caber en el dvd (lo cual ocurre bastantes veces) se cambiará de nuevo la capacidad a 4.38. Y así hasta que quepan. En mi caso muchas veces he llegado a 4.34. Sobre todo si son muchos los ficheros y hay diversidad de tamaños (no son todos más o menos iguales), porque estas dos variables son las que permiten ajustar más la grabación.
Otra novedad es que si se quiere grabar otro dvd diferente, no hay que volver a iniciar el programa, pues una opción permite hacerlo desde dentro.
No incluyo comentarios en el código, sólo los comentarios relativos a las  novedades, pues la primera vez que pegué el código ya los incluía.
Tampoco incluyo tabulaciones ni espacios en blanco porque la última vez a mí por lo menos no me permitieron compilar.
Se podría mejorar el programa para que se asegurase de que los datos tecleados o leídos del fichero se correspondan con el tipo de dato que almacena la variable. Por ejemplo, si se teclea 6t5.3 como tamaño de un archivo tendremos un error en tiempo de ejecución. Estoy investigando cómo resolver este problema (me parece que hay que hacer una directiva al compilador: {$ I-}). Estoy algo mal de tiempo y no sé cuando haré esta modificación. Cuando lo haga os lo comunicaré.
Un saludo.

------------
------------

{$codepage UTF8}

uses
crt;

var
opcion_tamano_archivo, opcion_nuevo_dvd: char;
opcion_nueva_capacidad_dvd, opcion_entrada_datos: char;
numero_archivos, numero_fichero_cambiar: byte;
posicion_avance, posicion_maximo: byte;
maximo: byte;
datos_archivos: text;
combinaciones: longint;
bucle_auxiliar, bucle_combinaciones: longint;
bucle_archivos_tomados, bucle_posiciones: byte;
bucle_ordenar_1, bucle_ordenar_2: byte;
vector_completo, vector_optimo: array of real;
vector_indices: array of byte;
suma_actual, suma_optima, capacidad: real;
auxiliar_ordenar: real;

function funcion_factorial (a, b: byte): qword;
var
producto: qword;
bucle: byte;
begin
producto:= 1;
for bucle:= a to b do
begin
producto:= producto * bucle;
end;
funcion_factorial:= producto;
end;

function funcion_combinaciones (n, m: byte): longint;
var
mayor, menor: byte;
numerador, denominador: qword;
begin
if m > (n - m) then
begin
mayor:= m;
menor:= n - m;
end
else
begin
mayor:= n - m;
menor:= m;
end;
numerador:= funcion_factorial (mayor + 1, n);
denominador:= funcion_factorial (1, menor);
funcion_combinaciones:= numerador div denominador;
end;

////////////////////////////////////////////////////////////
////////////////////Empieza el programa/////////////////////
////////////////////////////////////////////////////////////

begin

repeat //por si el usuario quiere grabar otro dvd
clrscr;

writeln ('OPTIMIZADOR DE GRABACIONES');
writeln ('==========================');

writeln;

{Damos la opción de leer datos de un archivo o teclearlos a mano}
writeln ('Para leer datos de un archivo pulsar "a"');
writeln ('Para teclear los datos pulsar otra tecla');
opcion_entrada_datos:= readkey;

if opcion_entrada_datos = 'a' then //si se leen de un archivo
begin
assign (datos_archivos, 'datos_archivos_grabacion');
reset (datos_archivos);

readln (datos_archivos, capacidad);

numero_archivos:= 0;

while not eof (datos_archivos) do
begin
numero_archivos:= numero_archivos + 1;
setlength (vector_completo, numero_archivos);
readln (datos_archivos, vector_completo [numero_archivos - 1]);
end;

close (datos_archivos);
end

else //si los datos se teclean a mano
begin
gotoxy(1,4);

for bucle_auxiliar:= 1 to 4 do
begin
writeln ('                                                   ');
end;

gotoxy(1,4);

writeln ('Introducción de datos');
writeln ('---------------------');

write ('Capacidad del dispositivo (en Gb): ');
readln (capacidad);

write ('Número de archivos a grabar (maximo 29): ');
readln (numero_archivos);

setlength (vector_completo, numero_archivos);

writeln ('Tamano de cada archivo (en Mb):');

for bucle_auxiliar:= 1 to numero_archivos do
begin
write ('   Archivo ', bucle_auxiliar,': ');
readln (vector_completo [bucle_auxiliar-1]);
end;

{Le damos al usuario la opción de que cambie el tamaño de algún
archivo, por si se equivocó al introducirlo}
repeat
writeln;
writeln ('Si quieres cambiar el tamañoo de algún fichero pulsa "s"');
writeln ('Si no quieres, pulsa otra tecla');
opcion_tamano_archivo:= readkey;

if opcion_tamano_archivo = 's' then
begin
write ('Número del fichero a cambiar: ');
readln (numero_fichero_cambiar);
write ('Escribe el nuevo tamaño: ');
readln (vector_completo [numero_fichero_cambiar - 1]);
end;
until opcion_tamano_archivo <> 's';
end; //else teclear datos a mano

{Vamos a ordenar los elementos de vector_completo de menor a mayor.
Utilizaremos el método de la burbuja ya que son pocos archivos}
for bucle_ordenar_1:= 0 to (numero_archivos - 2) do
begin
for bucle_ordenar_2:= (bucle_ordenar_1 + 1) to (numero_archivos - 1) do
begin
if vector_completo [bucle_ordenar_2] < vector_completo [bucle_ordenar_1] then
begin
auxiliar_ordenar:= vector_completo [bucle_ordenar_1];
vector_completo [bucle_ordenar_1]:= vector_completo [bucle_ordenar_2];
vector_completo [bucle_ordenar_2]:= auxiliar_ordenar;
end;
end;
end;

{Este repeat está por si el usuario quiere cambiar la capacidade del
dvd sin tener que volver a introducir todos los archivos}
repeat

suma_optima:= 0;

for bucle_archivos_tomados:= 1 to numero_archivos do
begin
setlength (vector_indices, bucle_archivos_tomados);
setlength (vector_optimo, bucle_archivos_tomados);
combinaciones:= funcion_combinaciones (numero_archivos, bucle_archivos_tomados);

for bucle_combinaciones:= 1 to combinaciones do
begin
suma_actual:= 0;

if bucle_combinaciones = 1 then
begin
for bucle_auxiliar:= 1 to bucle_archivos_tomados do
begin
vector_indices [bucle_auxiliar-1]:= bucle_auxiliar;
end;

end

else
begin
posicion_avance:= 0; posicion_maximo:= 0;

for bucle_posiciones:= bucle_archivos_tomados downto 1 do
begin
maximo:= numero_archivos - (bucle_archivos_tomados - bucle_posiciones);

if vector_indices [bucle_posiciones - 1] = maximo then
begin
posicion_maximo:= bucle_posiciones;
end

else
begin
if bucle_posiciones = bucle_archivos_tomados then
begin
vector_indices [bucle_posiciones-1]:= vector_indices [bucle_posiciones-1] + 1;
end

else
begin
if posicion_maximo = (bucle_posiciones + 1) then
begin
vector_indices [bucle_posiciones-1]:= vector_indices [bucle_posiciones-1] + 1;
posicion_avance:= bucle_posiciones;
end;
end;
end;
end;
end;

if posicion_avance <> 0 then
begin
for bucle_auxiliar:= (posicion_avance + 1) to bucle_archivos_tomados do
begin
vector_indices [bucle_auxiliar-1]:= vector_indices [bucle_auxiliar-2] + 1;
end;
end;

for bucle_auxiliar:= 1 to bucle_archivos_tomados do
begin
suma_actual:= suma_actual + vector_completo [vector_indices [bucle_auxiliar-1]-1];
end;

suma_actual:= suma_actual / 1024;

if (suma_actual < capacidad) and (suma_actual > suma_optima) then
begin
for bucle_auxiliar:= 1 to bucle_archivos_tomados do
begin
vector_optimo [bucle_auxiliar-1]:= vector_completo [vector_indices [bucle_auxiliar-1]-1];
end;
suma_optima:= suma_actual;
end;

end;

end;

clrscr;

writeln ('OPTIMIZADOR DE GRABACIONES');
writeln ('==========================');

writeln;

writeln ('Archivos seleccionados');
writeln ('----------------------');

for bucle_auxiliar:= 1 to numero_archivos do
begin
if vector_optimo [bucle_auxiliar-1] <> 0 then
begin
writeln (vector_optimo [bucle_auxiliar-1]:0:2);
end;
end;

writeln;

writeln ('Situación en el dispositivo de almacenamiento');
writeln ('---------------------------------------------');

writeln ('Capacidad: ', capacidad:0:2,' Gb');

writeln ('Espacio ocupado: ', suma_optima:0:4,' Gb');

writeln ('Espacio desperdiciado: ', (capacidad - suma_optima) * 1024 :0:2,' Mb');
writeln ('-----------------------------------------');

writeln;

{Permitimos al usuario introducir otra capacidad de dvd
por si la combinación óptima no cabe, ya que el tamaño
de los ficheros es una aproximación y en realidad son mayores}
writeln ('Si quieres cambiar la capacidad del actual DVD pulsa "s"');
writeln ('De lo contrario pulsa otra tecla');
opcion_nueva_capacidad_dvd:= readkey;

if opcion_nueva_capacidad_dvd = 's' then
begin
write ('Introduce la nueva capacidad (en Gb): ');
readln (capacidad);
end;

until opcion_nueva_capacidad_dvd <> 's'; //para otra capacidad

writeln;

{Para grabar un nuevo dvd con nuevos ficheros}
writeln ('Si quieres gravar otro DVD, pulsa "s"');
writeln ('Para salir del programa pulsa otra tecla');
opcion_nuevo_dvd:= readkey;

until opcion_nuevo_dvd <> 's'; //while para otro dvd

writeln;

writeln ('------ Programa finalizado ------');

writeln;

end.


30-Dec-2011 14:57
Nacho Cabanes (+83)

Gracias por compartirlo. :-)

Intuyo que has usado tabulaciones en vez de espacios, porque se ve todo pegado al margen izquierdo.  ;-)

En cuanto a los errores de conversión de cadena a número, basta con usar "val" para hallar el valor numérico, que devuelve dicho valor, pero también un código de error si no ha sido posible (en vez de interrumpir el programa).

Mira aquí:

http://www.aprendeaprogramar.com/mod/forum/discuss.php?d=246&parent=1171


31-Dec-2011 20:53
Fulanito de Tal

Gracias por el link.
No he puesto ni tabulaciones ni espacios. Cuando pegué el código por primera vez en este mismo hilo puse espacios en vez de tabulaciones y al intentar compilar no pude. Quité espacios y entonces sí que compiló.






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)