Das Rucksackproblem als Greedy Algorithmus

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

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

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()

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

Der Vorteil ist der relativ geringe Berechnungsaufwand durch die quadratische Komplexität $O(n^{2})$ . Das Problem ist aber, dass nicht die optimale Lösung gefunden wird.