Wikiversity

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

< Kurs:Algorithmen und Datenstrukturen | Vorlesung



Startseite
Vorlesung


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.


     

Abgerufen von „https://de.wikiversity.org/w/index.php?title=Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Beispiel:Rucksackproblem_Greedy&oldid=629018“