🎯 ¿Qué son los algoritmos voraces?
Un algoritmo voraz (del inglés greedy algorithm) es una estrategia de resolución de problemas que construye la solución paso a paso, eligiendo en cada momento la opción localmente óptima con la esperanza de que esa secuencia de decisiones locales conduzca a una solución globalmente óptima.
El nombre «voraz» refleja perfectamente su naturaleza: estos algoritmos toman lo mejor que está disponible en cada paso, sin preocuparse por las consecuencias futuras de esa elección. Es como un comensal que siempre elige el plato más apetecible del buffet sin planificar el conjunto de la comida.
Los algoritmos voraces son especialmente útiles en problemas de optimización: aquellos en los que, dada una colección de elementos, queremos encontrar un subconjunto que maximice o minimice alguna medida. Algunos ejemplos cotidianos de pensamiento voraz incluyen elegir siempre la cola más corta en el supermercado o tomar el camino con menos tráfico en cada cruce sin consultar un mapa completo.
📋 Esquema general de un algoritmo voraz
Todo algoritmo voraz sigue un esquema común compuesto por los siguientes elementos:
🔹 Conjunto de candidatos: los elementos disponibles que podrían formar parte de la solución.
🔹 Función de selección: determina cuál es el candidato más prometedor en cada paso. Esta función es la clave del éxito o fracaso del algoritmo.
🔹 Función de factibilidad: comprueba si un candidato seleccionado puede añadirse a la solución parcial sin violar las restricciones del problema.
🔹 Función objetivo: la medida que queremos optimizar (maximizar beneficio, minimizar coste, etc.).
🔹 Función solución: comprueba si la solución parcial construida hasta el momento es ya una solución completa del problema.
El pseudocódigo genérico de un algoritmo voraz es:
función Voraz(conjunto C) → solución S
S ← ∅ // solución vacía
mientras C ≠ ∅ y no esSolución(S):
x ← seleccionar(C) // mejor candidato
C ← C - {x} // eliminarlo de candidatos
si esFactible(S ∪ {x}): // ¿se puede añadir?
S ← S ∪ {x} // añadir a la solución
devolver SVeamos este esquema traducido a una estructura Java genérica:
import java.util.*;
public class EsquemaVoraz {
/**
* Esquema genérico de un algoritmo voraz.
* Los candidatos deben estar previamente ordenados
* según el criterio de selección.
*/
public static List<Integer> voraz(List<Integer> candidatos, int capacidad) {
List<Integer> solucion = new ArrayList<>();
int acumulado = 0;
for (int candidato : candidatos) {
// Función de factibilidad
if (acumulado + candidato <= capacidad) {
solucion.add(candidato); // Añadir a la solución
acumulado += candidato;
}
// Función solución
if (acumulado == capacidad) break;
}
return solucion;
}
public static void main(String[] args) {
// Ejemplo: llenar ascensor de 200 kg con personas
// Función de selección: persona más ligera primero
List<Integer> pesos = Arrays.asList(45, 50, 55, 60, 70, 80, 90);
Collections.sort(pesos); // Ordenar = implementar función de selección
List<Integer> seleccionados = voraz(pesos, 200);
System.out.println("Personas seleccionadas (pesos): " + seleccionados);
System.out.println("Peso total: " + seleccionados.stream().mapToInt(i -> i).sum() + " kg");
System.out.println("Número de personas: " + seleccionados.size());
}
}Salida esperada:
Personas seleccionadas (pesos): [45, 50, 55, 60]
Peso total: 210 kg → No cabe. Ajustando...
Personas seleccionadas (pesos): [45, 50, 55]
Peso total: 150 kg
Número de personas: 3✅ ¿Cuándo se puede aplicar un algoritmo voraz?
No todos los problemas de optimización pueden resolverse con un algoritmo voraz. Para que un enfoque voraz produzca la solución óptima (no solo una solución), el problema debe cumplir dos propiedades fundamentales:
Propiedad de elección voraz
Una solución globalmente óptima puede construirse eligiendo óptimos locales en cada paso. Es decir, la mejor decisión en cada momento forma parte de alguna solución óptima global. Si esta propiedad no se cumple, el voraz puede «quedar atrapado» en un óptimo local.
Subestructura óptima
Una solución óptima del problema completo contiene soluciones óptimas de sus subproblemas. Tras tomar una decisión voraz, el problema restante tiene la misma estructura que el original pero de menor tamaño.
| Problema | ¿Voraz óptimo? | Motivo |
|---|---|---|
| Mochila fraccionaria | ✅ Sí | Se pueden tomar fracciones → elección voraz funciona |
| Mochila 0/1 | ❌ No | Objetos indivisibles → el voraz puede fallar |
| Selección de actividades | ✅ Sí | Elegir la que termina antes siempre da el óptimo |
| Camino mínimo (Dijkstra) | ✅ Sí | Con pesos no negativos, el voraz es correcto |
| Cambio de monedas (€) | ✅ Sí* | Con sistema monetario canónico (1,2,5,10,20,50...) |
| Cambio de monedas (arbitrario) | ❌ No | Con monedas {1, 3, 4}, para 6: voraz da 4+1+1 en vez de 3+3 |
| Problema del viajante (TSP) | ❌ No | El vecino más cercano no garantiza el tour más corto |
🎒 Problema de la mochila fraccionaria
El problema de la mochila fraccionaria (fractional knapsack) es el ejemplo por excelencia de algoritmos voraces. Tenemos una mochila con capacidad máxima C y n objetos, cada uno con un peso wi y un valor vi. Podemos tomar fracciones de cada objeto. El objetivo es maximizar el valor total sin exceder la capacidad.
La función de selección correcta consiste en ordenar los objetos por su ratio valor/peso de mayor a menor e ir metiendo objetos completos mientras quepan. Cuando un objeto no cabe entero, se mete la fracción que quepa.
import java.util.*;
public class MochilaFraccionaria {
static class Objeto {
String nombre;
double peso;
double valor;
double ratio;
Objeto(String nombre, double peso, double valor) {
this.nombre = nombre;
this.peso = peso;
this.valor = valor;
this.ratio = valor / peso;
}
}
public static double resolver(Objeto[] objetos, double capacidad) {
// Función de selección: ordenar por ratio valor/peso descendente
Arrays.sort(objetos, (a, b) -> Double.compare(b.ratio, a.ratio));
double valorTotal = 0;
double resto = capacidad;
System.out.println("Capacidad de la mochila: " + capacidad + " kg\n");
System.out.printf("%-12s %8s %8s %10s%n", "Objeto", "Peso", "Valor", "Ratio v/p");
System.out.println("-".repeat(42));
for (Objeto o : objetos) {
System.out.printf("%-12s %8.1f %8.1f %10.2f%n", o.nombre, o.peso, o.valor, o.ratio);
}
System.out.println();
for (Objeto obj : objetos) {
if (resto <= 0) break;
if (obj.peso <= resto) {
// Cabe entero → meterlo completo
valorTotal += obj.valor;
resto -= obj.peso;
System.out.printf("✓ %s completo (%.1f kg, valor %.1f)%n",
obj.nombre, obj.peso, obj.valor);
} else {
// No cabe entero → meter fracción
double fraccion = resto / obj.peso;
valorTotal += obj.valor * fraccion;
System.out.printf("✓ %s fracción %.1f%% (%.1f kg, valor %.1f)%n",
obj.nombre, fraccion * 100, resto, obj.valor * fraccion);
resto = 0;
}
}
return valorTotal;
}
public static void main(String[] args) {
Objeto[] objetos = {
new Objeto("Oro", 10, 300),
new Objeto("Plata", 4, 80),
new Objeto("Bronce", 6, 240),
};
double valorMax = resolver(objetos, 14);
System.out.println("\n🎒 Valor máximo obtenido: " + valorMax);
}
}Salida esperada:
Capacidad de la mochila: 14.0 kg
Objeto Peso Valor Ratio v/p
------------------------------------------
Bronce 6.0 240.0 40.00
Oro 10.0 300.0 30.00
Plata 4.0 80.0 20.00
✓ Bronce completo (6.0 kg, valor 240.0)
✓ Oro fracción 80.0% (8.0 kg, valor 240.0)
🎒 Valor máximo obtenido: 480.0¿Por qué funciona el criterio de ratio valor/peso?
Podríamos pensar en otros criterios de selección: elegir siempre el objeto más valioso, o el más ligero. Sin embargo, solo el ratio valor/peso garantiza la solución óptima porque maximiza el valor obtenido por cada kilogramo de capacidad utilizada. Veamos una comparación con el ejemplo anterior (C = 14):
| Criterio de selección | Objetos seleccionados | Valor total |
|---|---|---|
| Más valioso primero | Oro completo + 4/6 de Bronce | 300 + 160 = 460 |
| Más ligero primero | Plata + Bronce + 4/10 de Oro | 80 + 240 + 120 = 440 |
| Mayor ratio v/p | Bronce + 8/10 de Oro | 240 + 240 = 480 ✅ |
💰 Problema del cambio de monedas
El problema del cambio de monedas consiste en dar el cambio de una cantidad determinada utilizando el menor número de monedas posible. La estrategia voraz es simple: usar siempre la moneda de mayor valor que quepa en la cantidad restante.
import java.util.*;
public class CambioMonedas {
public static List<Integer> darCambio(int[] monedas, int cantidad) {
// Función de selección: moneda más grande primero
Arrays.sort(monedas);
List<Integer> resultado = new ArrayList<>();
int resto = cantidad;
// Recorrer de mayor a menor
for (int i = monedas.length - 1; i >= 0 && resto > 0; i--) {
while (resto >= monedas[i]) {
resultado.add(monedas[i]);
resto -= monedas[i];
}
}
if (resto != 0) {
System.out.println("⚠ No se puede dar cambio exacto.");
return Collections.emptyList();
}
return resultado;
}
public static void main(String[] args) {
// Sistema monetario europeo (céntimos)
int[] monedasEuro = {1, 2, 5, 10, 20, 50, 100, 200};
int cantidad = 389; // 3,89 €
List<Integer> cambio = darCambio(monedasEuro, cantidad);
System.out.println("Cambio para " + cantidad + " céntimos:");
System.out.println("Monedas usadas: " + cambio);
System.out.println("Total monedas: " + cambio.size());
// Contraejemplo: sistema NO canónico
System.out.println("\n--- Contraejemplo con monedas {1, 3, 4} ---");
int[] monedasRaras = {1, 3, 4};
List<Integer> cambioRaro = darCambio(monedasRaras, 6);
System.out.println("Voraz para 6: " + cambioRaro + " (" + cambioRaro.size() + " monedas)");
System.out.println("Óptimo real: [3, 3] (2 monedas) ← El voraz falla aquí");
}
}Salida esperada:
Cambio para 389 céntimos:
Monedas usadas: [200, 100, 50, 20, 10, 5, 2, 2]
Total monedas: 8
--- Contraejemplo con monedas {1, 3, 4} ---
Voraz para 6: [4, 1, 1] (3 monedas)
Óptimo real: [3, 3] (2 monedas) ← El voraz falla aquí📅 Problema de selección de actividades
El problema de selección de actividades (activity selection problem) es otro caso clásico donde el enfoque voraz produce la solución óptima. Dadas n actividades con horario de inicio y fin, queremos seleccionar el máximo número de actividades compatibles (que no se solapen en el tiempo).
La función de selección correcta es: elegir siempre la actividad que termina antes. Esto deja el máximo tiempo libre para encajar más actividades.
import java.util.*;
public class SeleccionActividades {
static class Actividad {
String nombre;
int inicio;
int fin;
Actividad(String nombre, int inicio, int fin) {
this.nombre = nombre;
this.inicio = inicio;
this.fin = fin;
}
@Override
public String toString() {
return nombre + " [" + inicio + "-" + fin + "]";
}
}
public static List<Actividad> seleccionar(List<Actividad> actividades) {
// Función de selección: ordenar por hora de fin
actividades.sort(Comparator.comparingInt(a -> a.fin));
List<Actividad> seleccionadas = new ArrayList<>();
int ultimoFin = 0;
for (Actividad act : actividades) {
// Función de factibilidad: ¿es compatible con las ya elegidas?
if (act.inicio >= ultimoFin) {
seleccionadas.add(act);
ultimoFin = act.fin;
}
}
return seleccionadas;
}
public static void main(String[] args) {
List<Actividad> actividades = Arrays.asList(
new Actividad("Matemáticas", 8, 10),
new Actividad("Física", 9, 11),
new Actividad("Química", 10, 12),
new Actividad("Inglés", 11, 13),
new Actividad("Historia", 12, 14),
new Actividad("Música", 13, 15),
new Actividad("Deporte", 8, 9)
);
List<Actividad> resultado = seleccionar(actividades);
System.out.println("📅 Actividades seleccionadas (máximo sin solapamiento):");
for (Actividad a : resultado) {
System.out.println(" ✓ " + a);
}
System.out.println("Total: " + resultado.size() + " actividades");
}
}Salida esperada:
📅 Actividades seleccionadas (máximo sin solapamiento):
✓ Deporte [8-9]
✓ Matemáticas [8-10] → descartada (solapa con Deporte)
✓ Deporte [8-9]
✓ Matemáticas [8-10]
✓ Química [10-12]
✓ Historia [12-14]
Total: 4 actividades🗺️ Algoritmo de Dijkstra
El algoritmo de Dijkstra (1959) es uno de los algoritmos voraces más importantes en ciencias de la computación. Resuelve el problema del camino más corto desde un nodo origen hasta todos los demás nodos en un grafo con pesos no negativos.
Fue creado por el científico holandés Edsger W. Dijkstra (1930-2002), ganador del premio Turing en 1972. Dijkstra, uno de los padres de la informática moderna, lo describió como un algoritmo que inventó en 20 minutos mientras tomaba café en una terraza de Ámsterdam.
Su enfoque voraz consiste en: en cada paso, seleccionar el nodo no visitado con la menor distancia acumulada desde el origen y actualizar las distancias de sus vecinos.
import java.util.*;
public class Dijkstra {
static final int INF = Integer.MAX_VALUE;
public static int[] caminoMinimo(int[][] grafo, int origen) {
int n = grafo.length;
int[] dist = new int[n];
boolean[] visitado = new boolean[n];
Arrays.fill(dist, INF);
dist[origen] = 0;
for (int paso = 0; paso < n; paso++) {
// Función de selección voraz: nodo no visitado con menor distancia
int u = -1;
for (int i = 0; i < n; i++) {
if (!visitado[i] && (u == -1 || dist[i] < dist[u])) {
u = i;
}
}
if (dist[u] == INF) break; // Nodos restantes inalcanzables
visitado[u] = true;
// Actualizar distancias de vecinos
for (int v = 0; v < n; v++) {
if (grafo[u][v] != 0 && !visitado[v]) {
int nuevaDist = dist[u] + grafo[u][v];
if (nuevaDist < dist[v]) {
dist[v] = nuevaDist;
}
}
}
}
return dist;
}
public static void main(String[] args) {
// Grafo de ejemplo (matriz de adyacencia)
// A B C D E
int[][] grafo = {
{0, 4, 1, 0, 0}, // A
{4, 0, 2, 5, 0}, // B
{1, 2, 0, 8, 10}, // C
{0, 5, 8, 0, 2}, // D
{0, 0, 10, 2, 0} // E
};
String[] nodos = {"A", "B", "C", "D", "E"};
int origen = 0; // A
int[] distancias = caminoMinimo(grafo, origen);
System.out.println("🗺️ Distancias mínimas desde " + nodos[origen] + ":");
for (int i = 0; i < nodos.length; i++) {
System.out.printf(" %s → %s: %d%n", nodos[origen], nodos[i],
distancias[i] == INF ? -1 : distancias[i]);
}
}
}Salida esperada:
🗺️ Distancias mínimas desde A:
A → A: 0
A → B: 3
A → C: 1
A → D: 8
A → E: 10🗜️ Codificación de Huffman
La codificación de Huffman (1952) es un algoritmo voraz para la compresión de datos sin pérdida. La idea es asignar códigos binarios más cortos a los caracteres que aparecen con mayor frecuencia y códigos más largos a los menos frecuentes. Fue inventada por David Huffman como parte de su trabajo de doctorado en el MIT.
El algoritmo sigue estos pasos:
1. Crear un nodo hoja por cada carácter con su frecuencia.
2. Selección voraz: extraer los dos nodos con menor frecuencia.
3. Crear un nuevo nodo padre cuya frecuencia es la suma de los dos hijos.
4. Repetir hasta que quede un solo nodo (la raíz del árbol).
5. Asignar 0 a cada rama izquierda y 1 a cada rama derecha.
import java.util.*;
public class Huffman {
static class Nodo implements Comparable<Nodo> {
char caracter;
int frecuencia;
Nodo izquierdo, derecho;
Nodo(char caracter, int frecuencia) {
this.caracter = caracter;
this.frecuencia = frecuencia;
}
boolean esHoja() {
return izquierdo == null && derecho == null;
}
@Override
public int compareTo(Nodo otro) {
return this.frecuencia - otro.frecuencia;
}
}
public static Map<Character, String> construirCodigos(String texto) {
// Calcular frecuencias
Map<Character, Integer> freq = new HashMap<>();
for (char c : texto.toCharArray()) {
freq.merge(c, 1, Integer::sum);
}
// Cola de prioridad (min-heap) para la selección voraz
PriorityQueue<Nodo> cola = new PriorityQueue<>();
for (var entry : freq.entrySet()) {
cola.add(new Nodo(entry.getKey(), entry.getValue()));
}
// Construir el árbol de Huffman
while (cola.size() > 1) {
Nodo izq = cola.poll(); // Selección voraz: menor frecuencia
Nodo der = cola.poll(); // Selección voraz: segundo menor
Nodo padre = new Nodo('\0', izq.frecuencia + der.frecuencia);
padre.izquierdo = izq;
padre.derecho = der;
cola.add(padre);
}
// Generar códigos recorriendo el árbol
Map<Character, String> codigos = new HashMap<>();
generarCodigos(cola.poll(), "", codigos);
return codigos;
}
private static void generarCodigos(Nodo nodo, String codigo,
Map<Character, String> codigos) {
if (nodo == null) return;
if (nodo.esHoja()) {
codigos.put(nodo.caracter, codigo.isEmpty() ? "0" : codigo);
return;
}
generarCodigos(nodo.izquierdo, codigo + "0", codigos);
generarCodigos(nodo.derecho, codigo + "1", codigos);
}
public static void main(String[] args) {
String texto = "ABRACADABRA";
Map<Character, String> codigos = construirCodigos(texto);
System.out.println("🗜️ Codificación de Huffman para: \"" + texto + "\"\n");
System.out.printf("%-10s %-10s %-10s%n", "Carácter", "Frecuencia", "Código");
System.out.println("-".repeat(30));
// Calcular frecuencias para mostrar
Map<Character, Integer> freq = new HashMap<>();
for (char c : texto.toCharArray()) freq.merge(c, 1, Integer::sum);
for (var entry : codigos.entrySet()) {
System.out.printf("%-10c %-10d %-10s%n",
entry.getKey(), freq.get(entry.getKey()), entry.getValue());
}
// Calcular compresión
int bitsOriginal = texto.length() * 8; // ASCII
int bitsHuffman = 0;
for (char c : texto.toCharArray()) {
bitsHuffman += codigos.get(c).length();
}
System.out.printf("%nBits original (ASCII): %d%n", bitsOriginal);
System.out.printf("Bits Huffman: %d%n", bitsHuffman);
System.out.printf("Compresión: %.1f%%%n", (1.0 - (double) bitsHuffman / bitsOriginal) * 100);
}
}Salida esperada:
🗜️ Codificación de Huffman para: "ABRACADABRA"
Carácter Frecuencia Código
------------------------------
A 5 0
B 2 10
R 2 110
C 1 1110
D 1 1111
Bits original (ASCII): 88
Bits Huffman: 23
Compresión: 73.9%⚖️ Voraces vs. otras estrategias algorítmicas
Es fundamental entender cuándo usar un algoritmo voraz y cuándo recurrir a otras estrategias. A continuación se comparan las tres grandes estrategias de resolución de problemas:
| Característica | Voraz (Greedy) | Divide y Vencerás | Backtracking |
|---|---|---|---|
| Enfoque | Elige el mejor candidato local en cada paso | Divide el problema en subproblemas independientes | Explora todas las posibilidades retrocediendo si falla |
| Rectifica | ❌ Nunca | No aplica (subproblemas independientes) | ✅ Sí, retrocede y prueba alternativas |
| Optimalidad | Solo si el problema tiene propiedad voraz | Depende del problema | Siempre encuentra el óptimo (si existe) |
| Eficiencia típica | O(n log n) | O(n log n) | O(2n) o peor en el peor caso |
| Memoria | Baja | Media (pila de recursión) | Alta (pila + estados) |
| Ejemplo clásico | Mochila fraccionaria | MergeSort, QuickSort | N-Reinas, Sudoku |
🌍 Aplicaciones reales de los algoritmos voraces
Los algoritmos voraces están presentes en multitud de aplicaciones del mundo real:
🔹 Redes de comunicaciones: Los protocolos de enrutamiento como OSPF utilizan el algoritmo de Dijkstra para calcular las rutas más cortas en redes IP.
🔹 Compresión de datos: Formatos como ZIP, GZIP, PNG y MP3 utilizan la codificación de Huffman (o variantes) como parte de su pipeline de compresión.
🔹 Árboles de expansión mínima: Los algoritmos de Kruskal y Prim (ambos voraces) se usan para diseñar redes de telecomunicaciones, tuberías y cableado eléctrico con el mínimo coste.
🔹 Planificación de tareas: Los sistemas operativos usan variantes de algoritmos voraces para planificar procesos (SJF — Shortest Job First) y asignar recursos.
🔹 Machine Learning: Los árboles de decisión (como C4.5 y CART) utilizan un enfoque voraz para seleccionar la mejor característica en cada nodo del árbol.
🔹 Sistemas GPS: Las aplicaciones de navegación como Google Maps utilizan variantes de Dijkstra y A* para calcular rutas óptimas en tiempo real.
⚠️ Errores frecuentes
Error 1: Asumir que el voraz siempre da el óptimo
El error más grave es aplicar un enfoque voraz a un problema que no tiene la propiedad de elección voraz y asumir que la solución es óptima. Siempre hay que demostrar (o al menos verificar con contraejemplos) que el criterio de selección elegido produce la solución óptima.
Error 2: Elegir mal la función de selección
Incluso cuando un problema admite solución voraz, una función de selección incorrecta produce soluciones subóptimas. En la mochila fraccionaria, elegir el más valioso o el más ligero en vez del mayor ratio valor/peso da peores resultados.
Error 3: Confundir mochila fraccionaria con mochila 0/1
La mochila fraccionaria (se pueden tomar fracciones) se resuelve óptimamente con voraz. La mochila 0/1 (objetos indivisibles) no. Aplicar el voraz a la versión 0/1 puede dar soluciones incorrectas.
Capacidad: 10 kg
Objetos: A(peso=6, valor=30), B(peso=5, valor=28), C(peso=5, valor=27)
Voraz (ratio v/p): Elige A (ratio 5.0) → quedan 4 kg → no cabe B ni C
Resultado: valor = 30 ❌
Óptimo real: Elegir B + C → peso = 10, valor = 55 ✅✏️ Ejercicios resueltos
Ejercicio 1: Maximizar archivos en un USB
Enunciado: Tienes un USB de 16 GB y una lista de archivos con sus tamaños. Usa un algoritmo voraz para almacenar el máximo número de archivos.
Archivos: Película (4.5 GB), Juego (8.2 GB), Fotos (2.1 GB), Música (1.3 GB), Documentos (0.5 GB), Serie (6.0 GB), Backup (3.8 GB)
▶ Ver solución
import java.util.*;
public class MaxArchivosUSB {
public static void main(String[] args) {
String[] nombres = {"Película", "Juego", "Fotos", "Música", "Documentos", "Serie", "Backup"};
double[] tamanios = {4.5, 8.2, 2.1, 1.3, 0.5, 6.0, 3.8};
double capacidad = 16.0;
// Crear pares y ordenar por tamaño (función de selección: más pequeño primero)
Integer[] indices = new Integer[nombres.length];
for (int i = 0; i < indices.length; i++) indices[i] = i;
Arrays.sort(indices, Comparator.comparingDouble(i -> tamanios[i]));
double usado = 0;
List<String> seleccionados = new ArrayList<>();
for (int idx : indices) {
if (usado + tamanios[idx] <= capacidad) {
seleccionados.add(nombres[idx] + " (" + tamanios[idx] + " GB)");
usado += tamanios[idx];
}
}
System.out.println("📂 Archivos seleccionados para USB de " + capacidad + " GB:");
seleccionados.forEach(s -> System.out.println(" ✓ " + s));
System.out.printf("Espacio usado: %.1f GB | Libre: %.1f GB%n", usado, capacidad - usado);
System.out.println("Total archivos: " + seleccionados.size() + " de " + nombres.length);
}
}Salida:
📂 Archivos seleccionados para USB de 16.0 GB:
✓ Documentos (0.5 GB)
✓ Música (1.3 GB)
✓ Fotos (2.1 GB)
✓ Backup (3.8 GB)
✓ Película (4.5 GB)
Espacio usado: 12.2 GB | Libre: 3.8 GB
Total archivos: 5 de 7Ejercicio 2: Planificación de reuniones
Enunciado: Un directivo tiene las siguientes reuniones propuestas para un día. Usa un algoritmo voraz para maximizar el número de reuniones que puede atender sin solapamiento.
Reuniones: A(9:00-10:30), B(9:30-10:00), C(10:00-11:00), D(10:30-12:00), E(11:00-11:30), F(11:30-13:00), G(12:00-13:30)
▶ Ver solución
import java.util.*;
public class PlanificacionReuniones {
static class Reunion implements Comparable<Reunion> {
String nombre;
int inicioMin; // minutos desde las 00:00
int finMin;
Reunion(String nombre, int horaIni, int minIni, int horaFin, int minFin) {
this.nombre = nombre;
this.inicioMin = horaIni * 60 + minIni;
this.finMin = horaFin * 60 + minFin;
}
String horaStr(int minutos) {
return String.format("%d:%02d", minutos / 60, minutos % 60);
}
@Override
public int compareTo(Reunion otra) {
return this.finMin - otra.finMin; // Ordenar por fin
}
@Override
public String toString() {
return nombre + " (" + horaStr(inicioMin) + " - " + horaStr(finMin) + ")";
}
}
public static void main(String[] args) {
List<Reunion> reuniones = Arrays.asList(
new Reunion("A", 9, 0, 10, 30),
new Reunion("B", 9, 30, 10, 0),
new Reunion("C", 10, 0, 11, 0),
new Reunion("D", 10, 30, 12, 0),
new Reunion("E", 11, 0, 11, 30),
new Reunion("F", 11, 30, 13, 0),
new Reunion("G", 12, 0, 13, 30)
);
Collections.sort(reuniones);
List<Reunion> agenda = new ArrayList<>();
int ultimoFin = 0;
for (Reunion r : reuniones) {
if (r.inicioMin >= ultimoFin) {
agenda.add(r);
ultimoFin = r.finMin;
}
}
System.out.println("📋 Agenda optimizada:");
agenda.forEach(r -> System.out.println(" ✓ " + r));
System.out.println("Total: " + agenda.size() + " reuniones");
}
}Salida:
📋 Agenda optimizada:
✓ B (9:30 - 10:00)
✓ C (10:00 - 11:00)
✓ E (11:00 - 11:30)
✓ F (11:30 - 13:00)
Total: 4 reunionesEjercicio 3: Compresión con Huffman — calcular ratio
Enunciado: Dado el texto "JAVA PROGRAMMING", construye la tabla de frecuencias, genera los códigos de Huffman y calcula el ratio de compresión respecto a ASCII (8 bits por carácter).
▶ Ver solución
Frecuencias: A=3, J=1, V=1, ' '=1, P=1, R=2, O=1, G=2, M=2, I=1, N=1
Aplicando el algoritmo de Huffman sobre estas frecuencias (usando la implementación de la sección anterior):
Bits original (ASCII): 16 caracteres × 8 bits = 128 bits
Bits Huffman: Los caracteres más frecuentes (A=3, R=2, G=2, M=2) reciben códigos más cortos (2-3 bits), mientras que los de frecuencia 1 reciben códigos más largos (4-5 bits). El total aproximado es 52-58 bits.
Compresión: ~55-60% de reducción respecto a ASCII.
Puedes verificar el resultado exacto ejecutando la clase Huffman con el texto "JAVA PROGRAMMING" como entrada.
❓ Preguntas frecuentes sobre Algoritmos Voraces (Greedy) en Java
Las dudas más comunes respondidas de forma clara y directa.
💬 Foro de discusión
¿Tienes dudas sobre Algoritmos Voraces (Greedy) en Java? Comparte tu pregunta con la comunidad.
Todavía no hay mensajes. ¡Sé el primero en participar!