AlgDs WS99 Aufgabe 37.
Greedy-Algorithmus

Christian Semrau
mailto:Christian.Semrau@student.uni-magdeburg.de

  Das Problem:
 --------------

Wir haben einen Rucksack mit einer bestimmten Größe G.
Es liegen n Objekte da, jedes mit einer Größe g(i) und einem Wert w(i) 
(i=1..n). Die Summe der Größen g(i) sei größer als G.
Der relative Wert eines Objekts sei r(i) = w(i) / g(i).
Es darf angenommen werden, daß die relativen Werte sämtlich verschieden 
sind (es können 2 Objekte mit gleichem rel. Wert als ein Objekt betrachtet 
werden).
Es dürfen beliebige Teile a(i) ( 0 <= a(i) <= g(i) ) der Objekte in den 
Rucksack gepackt werden, so daß der Rucksack gefüllt ist ( Summe aller a(i) 
= G ) und der Gesamtwert W der Füllung maximal wird ( Summe aller [a(i) * 
r(i)] maximal ).

  Greedy-Algorithmus a:

Nimm jeweils das Objekt mit dem größten (absoluten) Wert und packe davon 
soviel wie möglich in den Rucksack, bis der Rucksack voll ist.

Daß dieser Algorithmus nicht immer das Optimum liefert, wird an einem 
Beispiel klar:

Rücksackgröße G=4
Objekt A: Größe g(1)=2, Wert w(1)=3, rel. Wert r(1)=1.5
Objekt B: Größe g(2)=5, Wert w(2)=6, rel. Wert r(2)=1.2

Nimm von Objekt B soviel wie möglich: a(2) = 4
Der Rucksack ist voll (also a(1) = 0), Gesamtwert W = 4.8
Bessere Lösung: a(1) = 2, a(2) = 2, Wert W = 5.4

  Die Lösung:
 -------------

  Greedy-Algorithmus b:
Nimm jeweils das Objekt mit dem größten relativen Wert und packe davon 
soviel wie möglich in den Rucksack, bis der Rucksack voll ist.

Daß dieser Algorithmus stets das Optimum liefert, versuche ich nun zu 
zeigen.


Wenn man die Teile der n Objekte unabhängig voneinander variiert, dann 
liegen die erlaubten Konfigurationen im Inneren und auf dem Rand eines n-
dimensionalen "Quaders", dessen eine Ecke im Koordinatenursprung liegt, die 
Kanten parallel zu den Koordinatenachsen, die Kantenlängen proportional zu 
den Größen der Objekte, und die gegenüberliegende Ecke abgeschnitten (durch 
die Größe des Rucksacks, einer "Ebene" senkrecht zur Hauptdiagonale).

Im Fall von 2 Objekten ergibt sich ein Quader ohne rechte obere Ecke,
bei 3 Objekten ein "normaler" Quader ohne rechte obere vordere Ecke (wenn 
der Ursprung links unten hinten liegt).
Das ist stets ein "konvexes" Gebiet.
(kleine Eselsbrücke: "Der Bauch vom T-Rex ist konvex." :-)

Die Gebiete mit gleichem Gesamtwert sind (n-1)-dim. "Ebenen", die alle 
parallel zueinander liegen.

Da die rel. Werte der Objekte verschieden sind, ist das Optimum eine Ecke 
des erlaubten Gebietes, und es gibt nur ein Optimum, nämlich das globale.

Bleibt noch zu zeigen, daß die von Algorithmus b gelieferte Konfiguration 
ein lokales Optimum bildet.

Diese Konfiguration sei gegeben durch die Teile a(i) der Objekte.
Das Objekt mit dem größten rel. Wert habe den Index j.
Wir wählen ein beliebiges Objekt (außer j), von dem nicht alles im Rucksack 
liegt, dessen Index sei k.
Wenn wir nun einen Teil von der Größe epsilon ( 0 < epsilon < min(a(j), 
g(k)-a(k)) ) des Objektes j aus dem Rucksack entfernen, und dafür 
genausoviel von k hineintun, dann sinkt der Gesamtwert um epsilon * r(j) 
und steigt dann um epsilon * r(k). Der Gesamtwert sinkt sich also um 
epsilon * (r(j)-r(k)). Da j das Objekt mit dem größten rel. Wert ist, ist 
r(j)>r(k) und der Gesamtwert sinkt.
Dasselbe funktioniert für eine beliebige Auswahl von m Objekten k(1)..k(m), 
von denen keins voll im Rucksack ist.
Denn man kann für jedes mögliche epsilon(1)..epsilon(m) den Austausch von j 
nach k(i) einzeln vollziehen, und jedesmal sinkt der Gesamtwert.

Daraus folgt also, das die optimale Konfiguration vom Objekt mit dem 
größten relativen Wert soviel wie möglich enthält.

Genauso kann man mit dem nächst-weniger-wertvollen Objekt fortfahren und 
die möglichen Austausche mit weniger wertvollen Objekten betrachten, und 
wieder sinkt jedesmal der Gesamtwert, d.h. daß dieses Objekt auch maximal 
eingepackt werden muß.
Das geht so fort bis zum am wenigsten wertvollen Objekt, und die optimale 
Konfiguration ist dann zwangsläufig die von Algorithmus b gelieferte.

-atempause-

Daß das jetzt keiner auf Anhieb verstanden hat, ist mir schon klar.
Das Beweisverfahren heißt daher auch "Beweis durch Einschüchterung" :-)
Macht euch nix draus, ich hab das hier nur flink zusammengeschrieben, um 
auch meinen Beitrag zur allgemeinen Vewirrung zu leisten.