Package de.hsrm.ads

Class RucksackBacktracking

java.lang.Object
de.hsrm.ads.RucksackBacktracking
public class RucksackBacktracking extends Object
Loesung des Rucksack Problems mit Backtracking
Version:
1.0 Creates a new RucksackBacktracking object.
Author:
Luca Krawczyk, Paul Knoll
See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static int
    counter
    Globaler Counter zur Ueberpruefung der Loesungen
    static int[]
    guteLoesung
    Globele Variable mit dem Array der aktuellen Loesung (0 = nicht ausgewaehlt, 1 = ausgewaehlt)
    static int
    guteLoesungWER
    Globele Variable mit dem Wert der aktuellen Loesung

  • Constructor Summary

    Constructors
    Constructor
    Description
    RucksackBacktracking()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    (package private) static int
    gesamtGewicht(int[] gewicht, int[] werte, int[] res, int maxGewicht)
    Berechnet das Gesamtgewicht der aktuellen Loesung.
    (package private) static int
    gesamtWert(int[] gewicht, int[] werte, int[] res, int maxGewicht)
    Berechnet das Gesamtwert der aktuellen Loesung.
    static void
    main(String[] args)
    Hauptmethode zum Starten des Backtracking Algorithmus.
    (package private) static int
    rucksack(int[] ausgewaehlt, int[] gewichte, int[] werte, int restKapa, int objIndex)
    Loest das Problem mit Backtracking.
    static void
    run(int[] gewichte, int[] werte, int[] ausgewaehlt)
    Hauptmethode zum Starten des Backtracking Algorithmus.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • guteLoesungWER

      public static int guteLoesungWER
      Globele Variable mit dem Wert der aktuellen Loesung

    • guteLoesung

      public static int[] guteLoesung
      Globele Variable mit dem Array der aktuellen Loesung (0 = nicht ausgewaehlt, 1 = ausgewaehlt)

    • counter

      public static int counter
      Globaler Counter zur Ueberpruefung der Loesungen

  • Constructor Details

    • RucksackBacktracking

      public RucksackBacktracking()

  • Method Details

    • gesamtGewicht

      static int gesamtGewicht(int[] gewicht, int[] werte, int[] res, int maxGewicht)
      Berechnet das Gesamtgewicht der aktuellen Loesung. Ist das Ergebnis groeßer als maxGewicht, wird -1 zurückgegeben.
      Parameters:
      gewicht - Liste der Gewichte
      werte - Liste der Werte der Gewichte
      res - Liste der aktuellen Loesung (auswahl von Gewichten)
      maxGewicht - Maximaler Gewichtsgrenzwert
      Returns:
      Gesamtgewicht der aktuellen Loesung oder -1, wenn das Gesamtgewicht groeßer als maxGewicht ist

    • gesamtWert

      static int gesamtWert(int[] gewicht, int[] werte, int[] res, int maxGewicht)
      Berechnet das Gesamtwert der aktuellen Loesung. Ist das Gewicht der aktuellen Loesung zu groß wird -1 zurückgegeben.
      Parameters:
      werte - Liste der Werte
      res - Liste der aktuellen Loesung (auswahl von Gewichten)
      maxGewicht - Maximaler Wertsgrenzwert
      gewicht - Liste der Gewichte
      Returns:
      Gesamtwert der aktuellen Loesung oder -1, wenn das Gesamtgewicht groeßer als maxGewicht ist

    • rucksack

      static int rucksack(int[] ausgewaehlt, int[] gewichte, int[] werte, int restKapa, int objIndex)
      Loest das Problem mit Backtracking. Diese Backtracking Implementierung beginnt bei der ersten Loesung und geht dann in alle moeglichen weiteren Loesungen vor. Hierbei wird das ausgewaehlt array von hinten aus verändert. Somit werden nach und nach Lösungen ausgeschlossen, die ungültig sind.
      Parameters:
      ausgewaehlt - Liste der aktuellen Loesung (auswahl von Gewichten)
      gewichte - Liste der Gewichte
      werte - Liste der Werte der Gewichte
      restKapa - Restkapazitaet
      objIndex - Index des Objekts, das gerade bearbeitet wird
      Returns:
      Wert der besten Loesung
      Throws:
      IndexOutOfBoundsException - Wenn die Anzahl der Objekte nicht gleich der Anzahl der Gewichte ist
      IndexOutOfBoundsException - Wenn die Anzahl der Objekte nicht gleich der Anzahl der Werte ist
      IndexOutOfBoundsException - Wenn die Anzahl der Objekte nicht gleich der Anzahl der aktuellen Loesung ist

    • run

      public static void run(int[] gewichte, int[] werte, int[] ausgewaehlt)
      Hauptmethode zum Starten des Backtracking Algorithmus.
      Parameters:
      gewichte - Liste der Gewichte
      werte - Liste der Werte der Gewichte
      ausgewaehlt - Liste der aktuellen Loesung (auswahl von Gewichten)

    • main

      public static void main(String[] args)
      Hauptmethode zum Starten des Backtracking Algorithmus.
      Parameters:
      args - keine Argumente