Kurs:Algorithmen und Datenstrukturen/Vorlesung/Beispiel:Rucksackproblem Greedy

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Das Rucksackproblem als Greedy Algorithmus[Bearbeiten]

Nun wird das Rucksackproblem mit dem Greedy Algorithmus gelöst. Wir erinnern uns, das Greedy-Grundprinzip ist es in jedem Berechnungsschritt die jeweils aktuell geeignetste Zwischenlösung zu verwenden. Angewandt auf unser Rucksackproblem bedeutet das, lege von den noch nicht im Rucksack befindlichen Gegenständen jeweils den „besten“ hinzu. Doch was ist der beste Gegenstand? Der nützlichste? Der leichteste? Der mit dem besten Verhältnis aus Nutzen und Gewicht?

Algorithmus nach Nutzen[Bearbeiten]

static Rucksack packeGierigNachNutzen() {
	Rucksack r = new Rucksack();
	while (true) {
		int pos=-1; int besterNutzen = 0;
		for (int i=0; i<auswahlObjekte.length; i++)
			if (r.auswahl[i] == false &&
				auswahlObjekte[i].nutzen > besterNutzen &&
				r.gewicht() + auswahlObjekte[i].gewicht <= 
					kapazitaet) {
			   besterNutzen = auswahlObjekte[i].nutzen;
			   pos = i;
			}
		if (pos == -1) break;
		else r.auswahl[pos] = true;
	}
	return r;
}

Algorithmus nach Gewicht[Bearbeiten]

static Rucksack packeGierigNachGewicht() {
	Rucksack r = new Rucksack();
	while (true) {
		int pos=-1; int bestesGewicht = MAX_GEWICHT+1;
		for (int i=0; i<auswahlObjekte.length; i++)
			if (r.auswahl[i] == false &&
				auswahlObjekte[i].gewicht < bestesGewicht &&
				r.gewicht() + auswahlObjekte[i].gewicht <= 
					kapazitaet) {
			   bestesGewicht = auswahlObjekte[i].gewicht;
			   pos = i;
			}
		if (pos == -1) break;
		else r.auswahl[pos] = true;
	}
	return r;
}

Aufruf in main()[Bearbeiten]

public static void main (String args[]) {
	if (args.length == 1)
		anzahlObjekte = Integer.parseInt(args[0]);
	kapazitaet = (int) (anzahlObjekte * MAX_GEWICHT / 4);
	auswahlObjekte = erzeugeObjekte();

	Rucksack r1 = packeGierigNachGewicht();
	System.out.println(Greedy Gewicht:  + r1);

	Rucksack r2 = packeGierigNachNutzen();
	System.out.println(Greedy Nutzen:  + r2);
	

Analyse[Bearbeiten]

Der Vorteil ist der relativ geringe Berechnungsaufwand durch die quadratische Komplexität . Das Problem ist aber, dass nicht die optimale Lösung gefunden wird.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg