Das Rucksackproblem

Hierbei handelt es sich um ein einfaches kombinatorisches Optimierungsproblem. Gegeben ist ein Rucksack mit der maximalen Kapazität C und n Gegenstände mit jeweils dem Gewicht $g_{i}$ und dem Wert $w_{i}$ . Gesucht wird die Auswahl der Gegenstände, so dass das Gesamtgewicht die Kapazität nicht überschreitet $\sum _{i\in I}g_{i}\leq C$ und die Summe der Werte maximal ist $\sum _{i\in I}w_{i}$ ist maximal. Es gibt dafür $2^{n}$ Möglichkeiten.

Generieren

zunächst werden die Objekte generiert:

 
public class Ding {
   public int gewicht, nutzen; 
   static private java.util.Random ra = new java.util.Random(); 

   // generieren
   Ding() { 
      gewicht = ra.nextInt(MAX_GEWICHT) + 1;
      nutzen = ra.nextInt(MAX_NUTZEN) + 1; 
   }
}

Es werden statische Variablen für die Problembeschreibung genutzt. Das Gewicht und der Nutzen der Objekte werden in einem eindimensionalem Array der Größe anzahlObjekte erstellt.

 
public class Rucksack {
   static int anzahlObjekte=10; 
   static ding [ ] auswahlObjekte = null; 
   …

Die Gewichte und Nutzwerte werden zufällig zwischen 1 und dem jeweiligem Maximalwert generiert.

 
static final int MAX_GEWICHT = 10;
static final int MAX_NUTZEN = 10;

Generierung der Auswahlobjekte:

 
static Ding [ ] erzeugeObjekte() {
   Ding[] r = new Ding[anzahlObjekte]; 
   for (int i = 0; i < anzahlObjekte; i++ ) {
      r[i] = new ding(); 
   } 
   return r;  
}
 …

Die Kapazität der Rucksäcke ist eine weitere statische Variable.

 
 static int kapazitaet;

Eine willkürlich gewählte Initialisierung der Main Methode ist:

 
kapazitaet = (int) (anzahlObjekte * MAX_GEWICHT / 4);

Dadurch passen im Schnitt nur die Hälfte der Gegenstände in den Rucksack.

Nun wird ein Rucksack als Auswahl der vorgegebene Dinge Implementiert, hierbei handelt es sich um die einzige nicht statische Variable.

 
 boolean[] auswahl = null;

Der Konstruktor zum Erzeugen einen leeren Rucksacks lautet:

 
Rucksack () {
   auswahl = new boolean [anzahlObjekte]; 
   for (int i = 0; i < anzahlObjekte; i++ ){
      auswahl[i] = false; 
   }
}

Es gibt einen Copy-Konstruktor zum Erzeugen einer Kopie eines existierenden Rucksacks. Die toString() Methode wird zur Ausgabe eines Rucksacks benutzt. Eine Methode zum Berechnen des Gesamtgewichts und des Gesamtnutzens lautet zum Beispiel:

 
int gewicht () {
   int g = 0; 
   for (int i=0; i < auswahl.length; i++ )
      if (auswahl[i] == true) 
         g = g + auswahlObjekte[i].gewicht; 
   return g; 
}

Index i	0	1	2	3	4	5
Gewicht	7	5	8	3	3	2
Nutzen	1	5	2	2	1	9

Rucksack 1 beinhaltet die Gegenstände 0,2 und 3, hatte ein Gesamtgewicht von 18 und einen Gesamtnutzen von 5.

Rucksack 1	T	F	T	T	F	F

Rucksack 2 beinhaltet die Gegenstände 1,2 und 5, hatte ein Gesamtgewicht von 15 und einen Gesamtnutzen von 16.

Rucksack 2	F	T	T	F	F	T

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Beispiel:Rucksackproblem

Das Rucksackproblem

Generieren