Inhaltsverzeichnis
Rucksack Problem oder auch "Knapsack Problem".
Am Rucksack Problem kann man die Vorteile des Backtrackings aufzeigen, da hier das globale Optimum gesucht wird.
Alles anzeigen
Am Rucksack Problem kann man die Vorteile des Backtrackings aufzeigen, da hier das globale Optimum gesucht wird.
Beispiel Backtracking
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);
- }
Weblinks
19.413 mal gelesen