¿Obteniendo una formulación matemática para mi solución recursiva?
En la pregunta tenemos elementos con diferentes valores, pero el peso de todos los elementos no importa. Tenemos un objetivo de beneficio que queremos alcanzar seleccionando esos elementos. Pero queremos tener la menor cantidad de elementos posibles y los elementos son infinitos.
Digamos que nuestro objetivo es 10 y tenemos elementos con valores de 1, 2, 3, 4. Queremos tener 4, 4, 2 en lugar de 3, 3, 3, 1. Tienen el mismo valor total, pero lo que queríamos era la menor cantidad de elementos con el mismo beneficio.
Ya he derivado métodos dinámicos y recursivos para resolverlo, pero el problema para mí es que no puedo derivar una fórmula matemática para mi método recursivo.
Aquí está mi método recursivo:
static int recursiveSolution(int[] values, int goal, int totalAmount) {
if (goal == 0)
return totalAmount;
if (goal < 0)
return Integer.MAX_VALUE;
totalAmount++;
int minAmount = Integer.MAX_VALUE;
for (int i = 0; i < values.length; i++) {
minAmount = Math.min(minAmount, recursiveSolution(values, goal - values[i], totalAmount));
}
return minAmount;
}
davy.ai
El problema descrito aquí se conoce como el problema de la mochila ilimitada (unbounded knapsack problem), donde podemos elegir una cantidad ilimitada de cada artículo y nuestro objetivo es maximizar el valor mientras dejamos de lado la restricción de peso. La dificultad para derivar una fórmula matemática para el método recursivo se debe a su naturaleza recursiva, lo que significa que la función no se declara explícitamente, sino que se define en función de sí misma.
El método dado funciona iterando sobre todos los artículos y reduciendo recursivamente la meta por sus valores hasta que la meta se convierte en cero o en un número negativo. Si la meta se vuelve negativa, significa que hemos excedido la ganancia objetivo y no podemos usar este conjunto de artículos, por lo que devolvemos un valor entero maximizado. Si la meta se convierte en cero, devolvemos el número total de artículos utilizados para alcanzar esa ganancia. Para cada llamada recursiva, consideramos el número mínimo de artículos utilizados para alcanzar la meta dada.
Una forma de derivar una fórmula matemática para el método recursivo es utilizar la programación dinámica, donde almacenamos el resultado de los cálculos previos y los utilizamos para optimizar cálculos posteriores. Uno de los enfoques es la técnica de memorización donde almacenamos el resultado de los subproblemas y los utilizamos cuando sea necesario en lugar de calcularlos nuevamente.
Para este problema en particular, podemos crear una tabla de tamaño (meta+1) y inicializarla con Integer.MAX_VALUE, excepto el primer índice, que establecemos en cero. Luego iteramos sobre todos los artículos y, para cada artículo, comenzamos desde su valor y actualizamos la tabla para todos los índices mayores o iguales a su valor, como el mínimo del valor anterior del índice y (1 + valor de la tabla en (índice actual – valor del artículo)). Finalmente, devolvemos el valor en el índice de la meta.
La complejidad temporal del método recursivo es exponencial, ya que se llama a sí mismo varias veces para cada artículo, lo que lleva a cálculos redundantes. Por otro lado, el enfoque de programación dinámica tiene una complejidad temporal de O(meta* n), donde n es el número de artículos, y calculamos solo una vez para cada índice.
En resumen, el problema dado requiere maximizar la ganancia minimizando el número de artículos, y podemos resolverlo a través del problema de la mochila ilimitada. El método recursivo funciona eficientemente pero no es adecuado para valores más grandes, y podemos derivar una fórmula matemática a través del enfoque de la programación dinámica.