El problema de la recolección de hierbas es un desafío algorítmico clásico que se puede modelar como una variante del problema de la Mochila 0/1. Se nos presenta un límite de tiempo total y una lista de diferentes hierbas. Cada hierba tiene un tiempo específico que se tarda en recolectar y un valor asociado. El objetivo es determinar la combinación de hierbas que un recolector puede adquirir para maximizar el valor total dentro del tiempo disponible, con la condición de que cada hierba solo se puede recolectar una vez.
1. Enfoque Codicioso (y su Fallo)
Una primera intuición al abordar este tipo de problemas de optimización podría ser un enfoque codicioso. Podríamos pensar en priorizar las hierbas que ofrecen el mayor valor por unidad de tiempo. Si ordenamos las hierbas de mayor a menor según su relación valer/tiempo y las recolectamos secuencialmente mientras el tiempo lo permita, ¿obtendríamos la solución óptima?
Consideremos el siguiente intento de solución utilizando una estrategia codiciosa:
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
// Estructura para representar una hierba
struct Hierba {
int tiempo_requerido;
int valor_obtenido;
double ratio_valor_tiempo; // Para el enfoque codicioso
// Constructor para facilitar la inicialización
Hierba(int t, int v) : tiempo_requerido(t), valor_obtenido(v) {
// Evitar división por cero si el tiempo requerido puede ser 0
ratio_valor_tiempo = (t == 0) ? static_cast<double>(v) : static_cast<double>(v) / t;
}
};
int main() {
std::ios_base::sync_with_stdio(false); // Optimización de I/O
std::cin.tie(NULL); // Optimización de I/O
int tiempo_total_disponible; // T en el problema original
int numero_hierbas; // M en el problema original
std::cin >> tiempo_total_disponible >> numero_hierbas;
std::vector<Hierba> lista_hierbas;
for (int i = 0; i < numero_hierbas; ++i) {
int t_item, v_item;
std::cin >> t_item >> v_item;
lista_hierbas.emplace_back(t_item, v_item);
}
// Ordenar las hierbas por el ratio valor/tiempo de forma descendente
std::sort(lista_hierbas.begin(), lista_hierbas.end(), [](const Hierba& a, const Hierba& b) {
return a.ratio_valor_tiempo > b.ratio_valor_tiempo;
});
long long valor_maximo_codicioso = 0; // Usar long long para valores potenciales grandes
// Recolectar hierbas según la estrategia codiciosa
for (const auto& h : lista_hierbas) {
if (tiempo_total_disponible >= h.tiempo_requerido) {
valor_maximo_codicioso += h.valor_obtenido;
tiempo_total_disponible -= h.tiempo_requerido;
}
}
std::cout << valor_maximo_codicioso << std::endl;
return 0;
}
Aunque esta estratgeia parece prometedora a primera vista, fallará en la mayoría de los casos de prueba. La razón es que una elección localmente óptima (tomar la hierba con el mejor ratio) no garantiza una solución globalmente óptima. Por ejemplo, podríamos tener una hierba con un ratio muy alto que consume casi todo el tiempo, impidiendo la recolección de múltiples hierbas con ratios ligeramente inferiores que, en conjunto, producirían un valor total mucho mayor.
2. Solución con Programación Dinámica: Mochila 0/1
Dado que cada hierba solo se puede recolectar una vez y buscamos maximizar un valor bajo una restricción de capacidad (tiempo), este problema es una clara aplicación de la Programación Dinámica, específicamente el problema de la Mochila 0/1.
La esencia del problema de la Mochila 0/1 radica en que para cada objeto (hierba en este caso), tenemos dos opciones: incluirlo en la mochila (recolectarlo) o no incluirlo. Debemos tomar estas decisiones de manera que se maximice el valor total sin exceder la capacidad (tiempo).
2.1. Definición del Estado
Definimos una tabla dp (o memo) donde dp[i][j] representará el valor máximo que podemos obtener al considerar las primeras i hierbas, utilizando exactamente j unidades de tiempo.
i: Índice de la hierba actual que estamos considerando (desde 1 hasta el número total de hierbas).j: Tiempo disponible actual (desde 0 hasta el tiempo total permitido).
2.2. Ecuación de Transición (Recurrencia)
Para calcular dp[i][j], consideramos la i-ésima hierba (con tiempo t_i y valor v_i):
- Caso 1: No tomamos la
i-ésima hierba. En este caso, el valor máximo es el mismo que el obtenido considerando las primerasi-1hierbas con el mismo tiempoj. Es decir,dp[i-1][j]. - Caso 2: Tomamos la
i-ésima hierba. Esto solo es posible si tenemos suficiente tiempo disponible (j >= t_i). Si la tomamos, el valor total sería el valor de lai-ésima hierba (v_i) más el valor máximo que pudimos obtener considerando las primerasi-1hierbas con el tiempo restante (j - t_i). Es decir,dp[i-1][j - t_i] + v_i.
La ecuación de recurrencia será el máximo de estos dos casos:
dp[i][j] = max(dp[i-1][j], dp[i-1][j - t_i] + v_i) // Si j >= t_i
dp[i][j] = dp[i-1][j] // Si j < t_i
2.3. Casos Base
Inicializamos dp[0][j] = 0 para todo j (si no consideramos ninguna hierba, el valor es 0) y dp[i][0] = 0 para todo i (si no tenemos tiempo, no podemos recolectar nada).
2.4. Implementación en 2D
#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_HIERBAS = 1005; // M_max + 5
const int MAX_TIEMPO_TOTAL = 1005; // T_max + 5
int dp_valores[MAX_HIERBAS][MAX_TIEMPO_TOTAL]; // dp_valores[idx_hierba][tiempo_actual]
int tiempos_hierbas[MAX_HIERBAS];
int valores_hierbas[MAX_HIERBAS];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int tiempo_limite; // T
int cantidad_hierbas; // M
std::cin >> tiempo_limite >> cantidad_hierbas;
for (int i = 1; i <= cantidad_hierbas; ++i) {
std::cin >> tiempos_hierbas[i] >> valores_hierbas[i];
}
// Llenar la tabla DP
for (int i = 1; i <= cantidad_hierbas; ++i) { // Iterar sobre cada hierba
for (int j = 0; j <= tiempo_limite; ++j) { // Iterar sobre cada posible tiempo
// Opción 1: No tomar la hierba 'i'
dp_valores[i][j] = dp_valores[i-1][j];
// Opción 2: Tomar la hierba 'i', si hay suficiente tiempo
if (j >= tiempos_hierbas[i]) {
dp_valores[i][j] = std::max(dp_valores[i][j],
dp_valores[i-1][j - tiempos_hierbas[i]] + valores_hierbas[i]);
}
}
}
// El resultado final es el valor máximo considerando todas las hierbas
// y el tiempo_limite completo
std::cout << dp_valores[cantidad_hierbas][tiempo_limite] << std::endl;
return 0;
}
3. Optimización de Espacio (DP en 1D)
Observando la ecuación de transición, notamos que dp[i][j] solo depende de los valores de la fila anterior dp[i-1]. Esto nos permite optimizar el espacio de una matriz 2D a un solo arreglo 1D. La idea es que el arreglo 1D dp_opt[j] represente el valor máximo para el tiempo j, considerando las hierbas procesadas hasta el momento.
Para cada nueva hierba i, actualizamos el arreglo dp_opt. La clave para la actualización correcta es iterar el tiempo j desde el tiempo_limite hacia abajo hasta el tiempo_requerido de la hierba actual. Si iteramos hacia arriba, dp_opt[j - tiempos_hierbas[i]] ya estaría actualizado con la hierba i, lo que efectivamente permitiría recolectar la misma hierba varias veces (convirtiendo el problema en Mochila Ilimitada).
3.1. Implementación en 1D
#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_TIEMPO_TOTAL = 1005; // Basado en T_max = 1000
const int MAX_HIERBAS = 1005; // Basado en M_max = 1000
int dp_valores_opt[MAX_TIEMPO_TOTAL]; // dp_valores_opt[tiempo_actual]
int tiempos_hierbas_arr[MAX_HIERBAS];
int valores_hierbas_arr[MAX_HIERBAS];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int tiempo_limite;
int cantidad_hierbas;
std::cin >> tiempo_limite >> cantidad_hierbas;
for (int i = 1; i <= cantidad_hierbas; ++i) {
std::cin >> tiempos_hierbas_arr[i] >> valores_hierbas_arr[i];
}
// Llenar el arreglo DP 1D
// Cada iteración 'i' representa considerar la i-ésima hierba
for (int i = 1; i <= cantidad_hierbas; ++i) {
int tiempo_actual_hierba = tiempos_hierbas_arr[i];
int valor_actual_hierba = valores_hierbas_arr[i];
// Iterar el tiempo 'j' de forma descendente
for (int j = tiempo_limite; j >= tiempo_actual_hierba; --j) {
// dp_valores_opt[j] = max(no tomar hierba i, tomar hierba i)
// 'no tomar hierba i' ya está representado por dp_valores_opt[j] de la iteración anterior 'i-1'
// 'tomar hierba i' es dp_valores_opt[j - tiempo_actual_hierba] + valor_actual_hierba
dp_valores_opt[j] = std::max(dp_valores_opt[j],
dp_valores_opt[j - tiempo_actual_hierba] + valor_actual_hierba);
}
}
// El resultado final es el valor máximo para el tiempo_limite completo
std::cout << dp_valores_opt[tiempo_limite] << std::endl;
return 0;
}
4. Optimización Adicional: Sin Almacenamiento Intermedio de Hierbas
Podemos optimizar aún más la memoria si no necesitamos almacenar todos los tiempos y valores de las hierbas en arreglos separados. En cambio, podemos leer cada hierba y aplicarla directamente al arreglo DP 1D.
#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_CAPACIDAD = 1005; // Corresponde al tiempo total máximo (T_max = 1000)
// Array DP para almacenar los valores máximos para cada capacidad (tiempo)
int valores_maximos[MAX_CAPACIDAD];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int capacidad_mochila; // Equivale al tiempo_limite (T)
int cantidad_objetos; // Equivale al numero_hierbas (M)
std::cin >> capacidad_mochila >> cantidad_objetos;
// Iterar sobre cada objeto (hierba)
for (int i = 0; i < cantidad_objetos; ++i) {
int peso_objeto; // Equivale al tiempo_requerido de la hierba
int valor_objeto; // Equivale al valor_obtenido de la hierba
std::cin >> peso_objeto >> valor_objeto;
// Actualizar el arreglo DP 1D
// Iterar la capacidad (tiempo) de forma descendente para asegurar la semántica 0/1
for (int j = capacidad_mochila; j >= peso_objeto; --j) {
valores_maximos[j] = std::max(valores_maximos[j],
valores_maximos[j - peso_objeto] + valor_objeto);
}
}
// El resultado final es el valor máximo que se puede obtener
// con la capacidad total de la mochila (tiempo_limite)
std::cout << valores_maximos[capacidad_mochila] << std::endl;
return 0;
}