Este tipo de problemática está resuelto satisfactoriamente desde hace 60 años o más, si bien adaptarlo a cada situación es lo que puede tener su miga.
La solución está en los árboles de Huffman, pero además no en uno simple si no en uno adaptativo.
Como supongo, sabrás, los árboles de Huffman se utilizan para la compresión de datos con el algoritmo que lleva su nombre... (inical y principalmente), donde el byte (valor más repetido) se le otorga pesos en función de su frecuencia.
...cuando es adapatativo señala que la frecuencia se actualiza con cada aparición (lectura de cada byte) lo que fuerza a actualizar el árbol: Si un nodo (le siendo sumado) supera en frecuencia al previo, desde ese instante, ese valor (el byte aparecido), se codifica con el valor que tiene asignado la posición del nodo...
Nota, que no es necesario reproducir en todo el algoritmo solo la parte que construye el árbol y la parte que lo hace adaptativo.
Un árbol de Huffman, típicamente se construye al inicio y luego se usa... pero en tu caso conviene que sea adaptativo, pués una vez que envías un emisor a un colector, el total de colector aumenta, luego tiene menos capacidad libre y por tanto bajaría en el nodo si ahora tiene menos disponibilidad libre que otro colector.
Algunas diferencias hay... en tu caso cuando un colector se llena, se supone (intuyo porque eso lo indicará la especificación completa del problema), deja de ser utilizado, lo que de algún modo implicaría retirar dicho nodo del árbol (y si existe un factor tiempo (u otro) que luego lo rehabilita, pués hale tocará añadirlo en su posición cuando se habilite superando a todos los nodos por 'espacio libre en toneladas'... Lo mismo si se añade un colector de repente al árbol... es decir necesitarás alguna función añadir colector(peso)... que examine que posición le corresponde en base a su 'espacio libre' en toneladas... es mejor abstraerse de toneladas, basura y tal y atenerse meramente al asunto matemático...
Un árbol de Huffman, netamente es un árbol binario que funciona conducido por el peso de los nodos, es decir el valor se establece al inicio... (en tu caso al inicio supone establecer el total que puede almacenar cada colector o si ya está usado, lo que le queda libre) y como he dicho precisa ser adaptativo... en Huffman adaptativo es costoso en tiempo ya que está continuamente actualizándose con cada byte... otro modo es 'semiadaptativo', es decir se propone (por ejemplo 4kb., 64kb. de bytes), se van sumando mientras y cuando se completa esa cantidad se reordena el árbol, conforma los nuevos valores... La compresión lograda con un algoritmo adaptativo es superior a los otros semiadaptativo o no adaptativo, pero el coste en tiempo es mayor.
Debes establecer en función de la cantidad de colectores y frecuencia en emisiones si en tu caso conviene que sea adaptativo o semiadaptativo, y si es semiadaptativo, debe encontrarse el punto aceptable para actualizar el árbol... (por ejemplo, cada 10 emisiones).
Todavía operar con árboles resulta lento, más siendo adaptativo... la opción más efectiva es operar sobre un array. Un array puede representar a un árbol binario, básicamente cada nodo de un árbol binario viene representado en un índice específico del array... un pequeño cálculo permite pasar de un nodo a otro. Así en vez de usar referencias a 'siguiente' anterior', 'derecha' o 'izquierda', tu tendrás sendas funciones que devuelvan el índice correspondiente dado aqule en el que estás y el acceso al que tratas de llegar...
Nota finalmente como un árbol, retiene la info que pedías al comienzo, pero sin necesitar un indicador otro que la que representa su posición y que obedece a su valor, al valor que alamcena que en tu caso debe ser el espacio libre o más complejo en función del espacio libre y el costo asociado...
...y finalmente ese array utilizado como un árbol binario, ofrece la velocidad que pueda ser preciso, aunque en el caso que te trae, considero que tiene menos sobrecarga que la simpre compresión de un fichero de 1Mb. (por ejemplo). Así que si finalmente construído el árol te funciona y satisface la velocidad y sobrecarga, podrías no necesitar el array... ya valorarás el caso.
Así que una vez te empapes sobre construir el árgol de Huffman y lograr que sea adaptativo, y luego (que funciones bien) remplazarlo por el array, finalmente te queda solventar la cuestión del costo (pesos de cada nodo). Ahí ya es cosa que tendrás que lidiar con la especificación que te hayan dado. Si el ejemplo es real (no un ejercicio), probablemente el costo será dado en kilometraje o en tiempo, etc... pero como digo, antes de meterte en el fregado de dar los pesos al árbol, primero constrúyelo con valores ficitios, no calculados, para verificar que el algortimo funciona bien que se actualiza convenientemente, y solo al final toca sustituir esa parte por la que en efecto calcula el peso real de cada nodo... en el árbol de Huffman esa parte es la más sencilla, pués se lleva la cuenta de la presencia de cada byte. Para grandes cantidades de datos, cuando el valor en la raíz supera cierto umbral para evitar desbordamiento del tipo de datos, suele recurrirse a dividirse todos (el valor de cada nodo) por la mitad... es decir ciertos detalles no son tu caso, otros son ligeramente variados y otros se aplican al 100%...
Bueno, ya tienes pan para ir comiendo... Si tienes alguna duda, pregunta... pero ven ya con algo más sólido...
La solución está en los árboles de Huffman, pero además no en uno simple si no en uno adaptativo.
Como supongo, sabrás, los árboles de Huffman se utilizan para la compresión de datos con el algoritmo que lleva su nombre... (inical y principalmente), donde el byte (valor más repetido) se le otorga pesos en función de su frecuencia.
...cuando es adapatativo señala que la frecuencia se actualiza con cada aparición (lectura de cada byte) lo que fuerza a actualizar el árbol: Si un nodo (le siendo sumado) supera en frecuencia al previo, desde ese instante, ese valor (el byte aparecido), se codifica con el valor que tiene asignado la posición del nodo...
Nota, que no es necesario reproducir en todo el algoritmo solo la parte que construye el árbol y la parte que lo hace adaptativo.
Un árbol de Huffman, típicamente se construye al inicio y luego se usa... pero en tu caso conviene que sea adaptativo, pués una vez que envías un emisor a un colector, el total de colector aumenta, luego tiene menos capacidad libre y por tanto bajaría en el nodo si ahora tiene menos disponibilidad libre que otro colector.
Algunas diferencias hay... en tu caso cuando un colector se llena, se supone (intuyo porque eso lo indicará la especificación completa del problema), deja de ser utilizado, lo que de algún modo implicaría retirar dicho nodo del árbol (y si existe un factor tiempo (u otro) que luego lo rehabilita, pués hale tocará añadirlo en su posición cuando se habilite superando a todos los nodos por 'espacio libre en toneladas'... Lo mismo si se añade un colector de repente al árbol... es decir necesitarás alguna función añadir colector(peso)... que examine que posición le corresponde en base a su 'espacio libre' en toneladas... es mejor abstraerse de toneladas, basura y tal y atenerse meramente al asunto matemático...
Un árbol de Huffman, netamente es un árbol binario que funciona conducido por el peso de los nodos, es decir el valor se establece al inicio... (en tu caso al inicio supone establecer el total que puede almacenar cada colector o si ya está usado, lo que le queda libre) y como he dicho precisa ser adaptativo... en Huffman adaptativo es costoso en tiempo ya que está continuamente actualizándose con cada byte... otro modo es 'semiadaptativo', es decir se propone (por ejemplo 4kb., 64kb. de bytes), se van sumando mientras y cuando se completa esa cantidad se reordena el árbol, conforma los nuevos valores... La compresión lograda con un algoritmo adaptativo es superior a los otros semiadaptativo o no adaptativo, pero el coste en tiempo es mayor.
Debes establecer en función de la cantidad de colectores y frecuencia en emisiones si en tu caso conviene que sea adaptativo o semiadaptativo, y si es semiadaptativo, debe encontrarse el punto aceptable para actualizar el árbol... (por ejemplo, cada 10 emisiones).
Todavía operar con árboles resulta lento, más siendo adaptativo... la opción más efectiva es operar sobre un array. Un array puede representar a un árbol binario, básicamente cada nodo de un árbol binario viene representado en un índice específico del array... un pequeño cálculo permite pasar de un nodo a otro. Así en vez de usar referencias a 'siguiente' anterior', 'derecha' o 'izquierda', tu tendrás sendas funciones que devuelvan el índice correspondiente dado aqule en el que estás y el acceso al que tratas de llegar...
Nota finalmente como un árbol, retiene la info que pedías al comienzo, pero sin necesitar un indicador otro que la que representa su posición y que obedece a su valor, al valor que alamcena que en tu caso debe ser el espacio libre o más complejo en función del espacio libre y el costo asociado...
...y finalmente ese array utilizado como un árbol binario, ofrece la velocidad que pueda ser preciso, aunque en el caso que te trae, considero que tiene menos sobrecarga que la simpre compresión de un fichero de 1Mb. (por ejemplo). Así que si finalmente construído el árol te funciona y satisface la velocidad y sobrecarga, podrías no necesitar el array... ya valorarás el caso.
Así que una vez te empapes sobre construir el árgol de Huffman y lograr que sea adaptativo, y luego (que funciones bien) remplazarlo por el array, finalmente te queda solventar la cuestión del costo (pesos de cada nodo). Ahí ya es cosa que tendrás que lidiar con la especificación que te hayan dado. Si el ejemplo es real (no un ejercicio), probablemente el costo será dado en kilometraje o en tiempo, etc... pero como digo, antes de meterte en el fregado de dar los pesos al árbol, primero constrúyelo con valores ficitios, no calculados, para verificar que el algortimo funciona bien que se actualiza convenientemente, y solo al final toca sustituir esa parte por la que en efecto calcula el peso real de cada nodo... en el árbol de Huffman esa parte es la más sencilla, pués se lleva la cuenta de la presencia de cada byte. Para grandes cantidades de datos, cuando el valor en la raíz supera cierto umbral para evitar desbordamiento del tipo de datos, suele recurrirse a dividirse todos (el valor de cada nodo) por la mitad... es decir ciertos detalles no son tu caso, otros son ligeramente variados y otros se aplican al 100%...
Bueno, ya tienes pan para ir comiendo... Si tienes alguna duda, pregunta... pero ven ya con algo más sólido...