Descripción
del problema
El problema consiste en llenar una mochila con unos
objetos dados. Cada objeto tiene un tamaño y un valor. Lo
que se quiere conseguir es maximizar la suma del
tamaño*valor de todos los objetos introducidos en
la mochila. En el caso de que un objeto no se pueda meter entero,
se fraccionará, quedando la mochila totalmente llena.
Limitaciones de la solución: El algoritmo esta
implementado utilizando un array, por lo que en la
búsqueda para obtener el mejor objeto, se recorren incluso
los elementos que ya han sido insertados en la mochila. El
algoritmo se podría mejorar utilizando una cola de
prioridad. Solución: Para resolver el
problema utilizamos un algoritmo voraz. Las principales
operaciones que realiza el algoritmo son:
- Seleccionar aquel objeto que mejor cumpla una
condición (se darán varias opciones al
usuario): - aquel objeto cuyo valor sea el máximo,
- el objeto de mínimo peso, o
- el objeto con mayor valor por unidad de peso.
- Colocar en la mochila el objeto entero, o una
fracción en el caso de que sea demasiado grande. - Detener el algoritmo, cuando la mochila este llena.
Los datos de los objetos (peso y valor), se cargan desde
un fichero de texto. La primera fila de dicho fichero contiene
los pesos de los objetos, y la segunda fila los valores, todos
ellos separados por espacios en blanco. En la solución
planteada, se permite llenar la mochila dependiendo del valor de
los objetos, el peso o el valor por unidad de peso, sin embargo,
sólo esta ultima condición, garantiza que la
solución sea
óptima.
Código fuente:
public class Mochila {
private float pesos[];
private float valores[];
private float pesoMaximo;
private boolean descartados[];
private float pctSeleccionados[];
private int numObjetos;
public Mochila(float pesos[], float valores[], float pesoMaximo) {
if (pesos.length != valores.length) {
throw new IllegalArgumentException("pesos.length != valores.length");
}
numObjetos = pesos.length;
this.pesos = pesos;
this.valores = valores;
this.pesoMaximo = pesoMaximo;
pctSeleccionados = new float[numObjetos];
descartados = new boolean[numObjetos];
}
public float[] getSolucion() {
return pctSeleccionados;
}
/*Se invoca al algoritmo según la función de selección
*SELECCIÓN: 1-Mayor valor 2-Menor peso 3- Mayor valor por unidad de peso
*Devuelve una matriz con los trozos a tomar de cada elemento (en orden)
*/
public float[] algoritmo(int seleccion) {
int i = 0;
float pesoActual = 0;
for (int j = 0; j < numObjetos; j++) {
pctSeleccionados[j] = 0; // 0% de cada objeto
descartados[j] = false; // todos disponibles
}
do {
System.out.println("Solicitamos nuevo objeto…");
System.out.println("pesoMaximo=" + pesoMaximo);
System.out.println("pesoActual=" + pesoActual);
i = mejorObjeto(seleccion);
System.out.println("pesos[" + (i + 1) + "]=" + pesos[i]);
if (pesoActual + pesos[i] <= pesoMaximo) {
System.out.println("pesoActual + pesos[" + (i + 1) + "] <= pesoMaximo");
pctSeleccionados[i] = 100; // se coge el objeto entero (100%)
pesoActual += pesos[i];
}
else {
System.out.println("npesoActual + pesos[" + (i + 1) + "] > pesoMaximo");
pctSeleccionados[i] = ( (pesoMaximo – pesoActual) * 100 / pesos[i]);
pesoActual = pesoMaximo;
}
System.out.println("npesoActualizado=" + pesoActual);
System.out.println("Cogemos el " + pctSeleccionados[i] +
"% del elemento " + (i + 1));
System.out.println(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>");
}
while (pesoActual < pesoMaximo);
return pctSeleccionados;
}
private int mejorObjeto(int seleccion) {
int indiceMejorObjeto = 0;
switch (seleccion) {
case 1: // Mayor valor
indiceMejorObjeto = maximoValor();
break;
case 2: // Menor peso
indiceMejorObjeto = minimoPeso();
break;
case 3: //Mayor valor por unidad de peso
indiceMejorObjeto = maximoValorPorUnidadDePeso();
break;
}
descartados[indiceMejorObjeto] = true;
return indiceMejorObjeto;
}
private int maximoValor() {
int indiceMejorObjeto = 0;
float maxValor = Float.MIN_VALUE;
for (int i = 0; i < numObjetos; i++) {
if (!descartados[i] && valores[i] > maxValor) {
indiceMejorObjeto = i;
maxValor = valores[i]; // se actualiza el maximo
}
}
return indiceMejorObjeto;
}
private int minimoPeso() {
int indiceMejorObjeto = 0;
float minPeso = Float.MAX_VALUE;
for (int i = 0; i < numObjetos; i++) {
if (!descartados[i] && pesos[i] < minPeso) {
indiceMejorObjeto = i;
minPeso = pesos[i]; // se actualiza el minimo
}
}
return indiceMejorObjeto;
}
private int maximoValorPorUnidadDePeso() {
int indiceMejorObjeto = 0;
float maxValorRelativo = Float.MIN_VALUE;
float valorRelativoActual;
for (int i = 0; i < numObjetos; i++) {
if (!descartados[i]) {
valorRelativoActual = valores[i] / pesos[i];
if (valorRelativoActual > maxValorRelativo) {
indiceMejorObjeto = i;
maxValorRelativo = valorRelativoActual; // se actualiza el maximo
}
}
}
return indiceMejorObjeto;
}
}
Complejidad: El caso peor supone que caben todos en la
mochila: O (n2).La complejidad se podría mejorar si los
objetos se almacenan en un montículo: O(n*Log(n))
Algoritmo
Heurístico
En computación, dos objetivos fundamentales para
la mayoría de casos son encontrar algoritmos con buenos
tiempos de ejecución y buenas soluciones, usualmente las
óptimas. Una heurística es un
algoritmo que ofrece uno o ambos objetivos; por ejemplo,
normalmente encuentran buenas soluciones, aunque en ocasiones no
hay pruebas de que la solución no pueda ser
arbitrariamente errónea; o se ejecuta razonablemente
rápido, aunque no existe tampoco prueba de que deba ser
así.
Página siguiente  |