1. Descripción del problema
2. Algoritmo Heurístico
3. Algoritmo de Kruskal
4. Casuística
5. Convergencia del problema

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í.