Rucksack Problem Algorithmus

Torben Brodt

Administrator

Lexicon articles: 104

Sunday, July 4th 2010, 2:33pm

Content

1. Beispiel Backtracking
2. Weblinks

Abstract

Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzenwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzenwert der ausgewählten Objekte maximiert werden.

Article

Rucksack Problem oder auch "Knapsack Problem".
Am Rucksack Problem kann man die Vorteile des Backtrackings aufzeigen, da hier das globale Optimum gesucht wird.

1. Beispiel Backtracking

Java Quellcode

public static void main(String[] args) {
	int[] werte = new int{5,4,3,2,1};
	int[] gewichte = new int{10,5,20,30,15};
}
 
public static int rucksack(int i, int kap, int wert) {
	if ((i >= n) || (kap <= 0))
		return wert;
	if (gewichte[i] > kap)
		return rucksack(i+1,kap,wert);
	int mit=rucksack(i+1, kap-gewichte[i], wert+werte[i]);
	int ohne=rucksack(i+1, kap, wert);
	return max(mit, ohne);
}