Ein einfacher Lösungsalgorithmus

Kombinationen ausprobieren

Eine - zugegebenermaßen - wenig elegante Lösung des Rucksackproblems besteht darin, alle möglichen Kombinationen von Gegenständen zu betrachten und die zugehörigen Gesamtgewichte und Gesamtwerte zu berechnen und aus all den ermittelten Zahlenwerten die gesuchte Kombination zu bestimmen.

Aufgabe 1

Betrachte den in der Abbildung gezeigten Fall, dass 10 Gegenstände zur Auswahl stehen. Wie viele verschiedene Kombinationen von Gegenständen gibt es? Zu den Kombinationen sollen auch solche Fälle wie keinen Gegenstand einpacken und alle Gegenstände einpacken zählen.

Ein Algorithmus zum Lösungsverfahren

Ein Algorithmus zur oben beschriebenen Idee lässt sich leicht formulieren, z.B. so:

ALGORITHMUS optimaleLoesung:
    Übergabe:
    erzeuge eine erste kombination, z.B. '00000000'
    maxKombination = kombination
    maxWert = Gesamtwert von kombination
    SOLANGE noch nicht alle Kombinationen durchlaufen sind:
        erzeuge eine neue kombination
        WENN der Gesamtwert von kombination > maxWert und
             das Gesamtgewicht von kombination <= grenzgewichtRucksack:
            maxKombination = kombination
            maxWert = Gesamtwert von kombination
    Rückgabe: (maxKombination, maxWert, Gesamtgewicht von maxKombination)

Eine Implementierung zum Algorithmus

Zur Implementierung müssen u.a. alle möglichen Kombinationen erzeugt werden. Wir gehen dabei so vor:

Eine Kombination wird durch eine 0-1-Zeichenkette beschrieben, die für jeden Gegenstand festlegt, ob er eingepackt wird ('1') oder nicht ('0'). So beschreibt z.B. die Zeichenkette '0010000000' eine Situation, in der nur der Gegenstand mit der Nummer 2 ausgewählt wird (beachte: wie fangen bei 0 an zu zählen).

Bei n Gegenständen gibt es 2ⁿ mögliche Kombinationen bzw. 0-1-Zeichenketten. Wir erzeugen diese systematisch, indem wir die Zahlen 0..2ⁿ-1 durchlaufen und aus den Dualdarstellungen dieser Zahlen die 0-1-Bitmuster generieren.

Das folgende (noch zu ergänzende) Demoprogramm bestimmt alle möglichen Kombinationen sowie deren Gesamtwert und Gesamtgewicht.

# Rucksackproblem

gegenstaende = [(3.5, 375), (2.5, 300), (2.0, 100), (3.0, 225), (1.0, 50), 
               (1.75, 125), (0.75, 75), (3.0, 275), (2.5, 150), (2.25, 50)]
grenzgewichtRucksack = 15.0

# Funktionen zur Erzeugung einer Lösung

def gesamtGewicht(kombination):
    # ...

def gesamtWert(kombination):
    # ...

def erzeugeKombinationAusZahl(zahl):
    kombination = bin(zahl)[2:]
    while len(kombination) < len(gegenstaende):
        kombination = '0' + kombination
    return kombination

def alleKombinationen():
    anzahlKombinationen = 2**len(gegenstaende)
    zahl = 0
    while zahl < anzahlKombinationen:
        kombination = erzeugeKombinationAusZahl(zahl)
        Ausgabe: (kombination, gesamtWert(kombination), gesamtGewicht(kombination))
        zahl = zahl + 1

def optimaleLoesung():
    # ...
    # return (maxKombination, maxWert, gesamtGewicht(maxKombination))

# Test
alleKombinationen()

Aufgabe 2

(a) Teste erst einmal die Funktion erzeugeKombinationAusZahl durch Funktionsaufrufe wie z.B. erzeugeKombinationAusZahl(73).

(b) Ergänze die Implementierung der Funktionen gesamtGewicht und gesamtWert. Teste diese Funktionen mit geeigneten Funktionsaufrufen..

(c) Teste anschließend die Hilfsprozedur alleKombinationen. Sie müsste alle möglichen Kombinationen sowie deren Gesamtwert und Gesamtgewicht erzeugen und ausgeben.

(d) Entwickle eine Implementierung der Funktion optimaleLoesung. Benutze dabei Teile der Hilfsprozedur alleKombinationen. Zur Kontrolle: Sie sollte das Ergebnis ('1101011100', 1375, 14.5) liefern.