Was sie in einem Interview fragen: Überprüfung von Algorithmen, Teil 1

Guten Abend allerseits! Verschiedene Arten von Algorithmen werden in Projekten häufiger eingesetzt, als Sie vielleicht denken. Beispielsweise müssen wir einige Daten nach bestimmten Parametern (Spalten) sortieren, damit wir ohne großen Aufwand darin navigieren können. Daher ist es nicht verwunderlich, dass man bei Vorstellungsgesprächen nach dem einen oder anderen Grundalgorithmus fragt und ihm vielleicht die Aufgabe gibt, ihn mithilfe von Code zu implementieren. Und da Sie auf dieser Seite sind, wage ich zu vermuten, dass Sie in Java schreiben. Deshalb lade ich Sie heute ein, sich mit einigen grundlegenden Algorithmen und konkreten Beispielen ihrer Implementierung in Java vertraut zu machen. Mit einigen meine ich:

1. Übersicht über Array-Sortieralgorithmen:
   • Blasensortierung,
   • Auswahlsortierung,
   • Sortieren durch Einfügen,
   • Muschelsortierung,
   • schnelle Sorte,
   • Zusammenführen, sortieren.
2. Gieriger Algorithmus.
3. Pathfinding-Algorithmen:
   • in die Tiefe kriechen
   • breites Kriechen.
4. Der Transportalgorithmus ist der Dijkstra-Algorithmus.

Nun, ohne weitere Umschweife, kommen wir zur Sache.

1. Übersicht über Sortieralgorithmen

Blasensortierung

Dieser Sortieralgorithmus ist vor allem für seine Einfachheit bekannt, weist aber gleichzeitig eine der niedrigsten Ausführungsgeschwindigkeiten auf. Betrachten Sie als Beispiel die Blasensortierung für Zahlen in aufsteigender Reihenfolge. Stellen wir uns eine Kette zufällig platzierter Zahlen vor, für die die folgenden Schritte ausgeführt werden, beginnend am Anfang der Kette:

• vergleiche zwei Zahlen;
• Wenn die Zahl links größer ist, dann vertauschen Sie sie.
• eine Position nach rechts verschieben.

Nachdem wir die gesamte Kette durchlaufen und diese Schritte ausgeführt haben, werden wir feststellen, dass die größte Zahl am Ende unserer Zahlenreihe steht. Als nächstes wird genau der gleiche Durchgang entlang der Kette durchgeführt, wobei die oben beschriebenen Schritte befolgt werden. Aber dieses Mal werden wir das letzte Element der Liste nicht einbeziehen, da es das größte ist und bereits an letzter Stelle steht, wie es sein sollte. Auch hier erhalten wir das letzte Element am Ende unserer betreffenden Zahlenreihe. Demnach werden die beiden größten Zahlen bereits auf ihren Plätzen sein. Und wieder beginnt der Durchgang entlang der Kette, wobei die bereits vorhandenen Elemente ausgeschlossen werden, bis alle Elemente in der erforderlichen Reihenfolge sind. Schauen wir uns die Implementierung der Blasensortierung im Java-Code an:

public class Solution {
   public static void main(String[] args) {
    int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
    bubbleSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void  bubbleSort(int[] array) {
       for(int i = array.length -1; i > 1; i--) {
         for (int j = 0; j < i; j++) { //
             if (array[j] > array[j+1]) {
                 int temp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = temp;
             }
         }
       }
   }
}

Wie Sie sehen, gibt es hier nichts Kompliziertes und alles scheint großartig zu sein, wenn da nicht ein „aber“ wäre ... Die Blasensortierung ist sehr, sehr langsam, mit einer Zeitkomplexität von O(N²) , da wir verschachtelt sind Schleifen. Der externe Durchlauf durch die Elemente wird N- mal durchgeführt, der interne ebenfalls N- mal, und als Ergebnis erhalten wir N*N , N² Iterationen. Sie können diese Art der Sortierung in diesem Artikel genauer untersuchen .

Sortierung nach Auswahl

Dieser Algorithmus ähnelt der Blasensortierung, arbeitet jedoch etwas schneller. Nehmen wir als Beispiel noch einmal eine Reihe von Zahlen, die wir in aufsteigender Reihenfolge anordnen möchten. Die Essenz des Algorithmus besteht darin, nacheinander alle Zahlen durchzugehen und das kleinste Element auszuwählen, das wir nehmen und mit dem Element ganz links (Element 0) tauschen. Hier erhalten wir eine ähnliche Situation wie bei der Blasensortierung, aber in diesem Fall ist das sortierte Element das kleinste. Daher beginnt der nächste Durchlauf durch die Elemente mit dem Element an Index 1. Auch diese Durchgänge werden wiederholt, bis alle Elemente sortiert sind. Implementierung in Java:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {

       for (int i = 0; i < array.length-1; i++) { // внешний обычный  цикл
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // вставка отссортиованного числа, в положеную ему ячейку
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

Dieser Algorithmus ist der Blasensortierung überlegen, da hier die Anzahl der notwendigen Permutationen von O(N²) auf O(N) reduziert wird: Wir schieben kein Element durch die gesamte Liste, aber trotzdem bleibt die Anzahl der Vergleiche O(N²). ) . Für diejenigen, die mehr über diesen Algorithmus erfahren möchten, empfehle ich dieses Material .

Sortieren durch Einfügen

Nehmen wir als Beispiel noch einmal eine Reihe von Zahlen, die wir in aufsteigender Reihenfolge anordnen möchten. Dieser Algorithmus besteht darin, eine Markierung zu platzieren, links davon werden die Elemente bereits teilweise untereinander sortiert. Bei jedem Schritt des Algorithmus wird eines der Elemente ausgewählt und an der gewünschten Position in der bereits sortierten Reihenfolge platziert. Der sortierte Teil wird also weiter wachsen, bis alle Elemente betrachtet wurden. Sie fragen sich vielleicht: Woher bekomme ich den Teil der Elemente, der bereits sortiert ist und nach dem Sie eine Markierung setzen müssen? Aber das Array des ersten Elements ist doch schon sortiert, oder? Schauen wir uns die Implementierung in Java an:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       insertionSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void insertionSort(int[] array) {

       for (int i = 1; i < array.length; i++) { // i - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного Element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Diese Art der Sortierung ist den oben beschriebenen überlegen, da dieser Algorithmus trotz gleicher Laufzeit – O(N²) – doppelt so schnell wie die Blasensortierung und etwas schneller als die Auswahlsortierung arbeitet. Lesen Sie hier mehr .

Muschelsortierung

Bei dieser Sortierung handelt es sich naturgemäß um eine modifizierte Einfügungssortierung. Worüber rede ich? Gehen wir der Reihe nach vor. Ein Schritt wird ausgewählt, und es gibt viele Ansätze für diese Auswahl. Wir werden nicht zu sehr auf dieses Thema eingehen. Teilen wir unser Array in zwei Hälften und erhalten eine bestimmte Zahl – das wird unser Schritt sein. Wenn wir also 9 Elemente im Array haben, beträgt unser Schritt 9/2 = 4,5 . Wir verwerfen den Bruchteil und erhalten 4 , da Array-Indizes nur Ganzzahlen sind. Mit diesem Schritt schaffen wir Verbindungen für unsere Gruppen. Wenn ein Element den Index 0 hat, ist der Index des nächsten Elements in seiner Gruppe 0+4 , also 4 . Das dritte Element hat einen Index von 4+4 , das vierte einen Index von 8+4 und so weiter. Für die zweite Gruppe ist das erste Element 1,5,9…. In der dritten und vierten Gruppe wird es genau gleich sein. Als Ergebnis erhalten wir aus der Zahlenreihe {6,3,8,8,6,9,4,11,1} vier Gruppen: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Sie behalten ihren Platz in der allgemeinen Reihe, aber für uns sind sie als Mitglieder derselben Gruppe gekennzeichnet: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Weiter innerhalb dieser Gruppen erfolgt die oben beschriebene Einfügungssortierung , wonach die Gruppen wie folgt aussehen: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Im allgemeinen Array bleiben die von den Gruppen besetzten Zellen gleich, aber die Reihenfolge innerhalb ihnen ändert sich entsprechend der Reihenfolge der oben genannten Gruppen: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Das Array ist etwas geordneter, nicht wahr? Der nächste Schritt wird durch 2 geteilt: 4/2 = 2 Wir haben zwei Gruppen: I - {1,4,6,8,6} II - {3,8,9,11} B allgemeines Array: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Wir gehen beide Gruppen mit dem Einfügungssortierungsalgorithmus durch und erhalten ein Array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Jetzt ist unser Array fast sortiert. Die letzte Iteration des Algorithmus bleibt bestehen: Wir teilen den Schritt durch 2: 2/2 = 1. Wir erhalten eine Gruppe, das gesamte Array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } By Wir durchlaufen den Einfügungssortierungsalgorithmus und erhalten: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Sehen wir uns an, wie wir diese Sortierung im Java-Code anzeigen können:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {
       int length = array.length;
       int step = length / 2;
       while (step > 0) {
           for (int numberOfGroup = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) {//Sortierung вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

Derzeit ist die Wirksamkeit der Shell-Sortierung nicht wirklich belegt, da die Ergebnisse in verschiedenen Situationen unterschiedlich sind. Die aus Experimenten erhaltenen Schätzungen reichen von O(N ^3/2 ) bis O(N ^7/6 ) .

Schnelle Sorte

Dies ist einer der beliebtesten Algorithmen und daher lohnt es sich, ihm besondere Aufmerksamkeit zu schenken. Der Kern dieses Algorithmus besteht darin, dass ein Pivot-Element aus einer Liste von Elementen ausgewählt wird – im Wesentlichen jedes Element, nach dem die verbleibenden Werte sortiert werden müssen. Werte kleiner als links, Werte größer als rechts. Als nächstes werden auch die rechten und linken Teile vom unterstützenden Element ausgewählt und das Gleiche passiert: Die Werte werden relativ zu diesen Elementen sortiert, dann werden die unterstützenden Elemente aus den resultierenden Teilen ausgewählt – und so weiter, bis wir eine Sortierung erhalten Reihe. Dieser Algorithmus in Java wird durch Rekursion implementiert:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       fastSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void fastSort(int[] array) {
       recursionFastSort(array, 0, array.length - 1);
   }


   public static void recursionFastSort(int[] array, int min, int max) {
       if (array.length == 0)// Zustand выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так Wie нечего уже делить
           return;


       int middle = min + (max - min) / 2;  // выбираем середину
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) {  // относительно Element middle определяемменьшие элементы слева, большие справа
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) {      //меняем местами
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // запускаем рекурсию с Elementми меньшими чем middle
           recursionFastSort(array, min, j);

       if (max > i)// запускаем рекурсию с Elementми большими чем middle
           recursionFastSort(array, i, max);
   }
}

Ohne Zweifel gilt der Quicksort-Algorithmus als der beliebteste, da er in den meisten Situationen in O(N*logN) -Zeit schneller als andere läuft .

Zusammenführen, sortieren

Auch diese Sortierung ist beliebt. Es bezieht sich auf eine der Arten von Algorithmen, die nach dem Prinzip „Teile und herrsche“ arbeiten: Bei ihnen teilen wir Aufgaben zunächst in minimale Teile auf ( Schnellsortierung ist auch ein Vertreter solcher Algorithmen ). Was ist also die Essenz dieses Algorithmus?

Aktie:

Das Array wird in zwei etwa gleich große Teile geteilt, jeder dieser beiden Teile wird in zwei weitere geteilt und so weiter, bis die kleinsten unteilbaren Teile übrig bleiben. Am wenigsten unteilbare Teile liegen vor, wenn jedes Array ein Element hat, was bedeutet, dass ein solches Array automatisch als sortiert betrachtet wird.

Erobern:

Hier beginnt der Prozess, der dem Algorithmus seinen Namen gibt – das Merging . Nehmen Sie dazu die beiden resultierenden geordneten Arrays und führen Sie sie zu einem zusammen. In diesem Fall wird das kleinste der ersten Elemente der beiden Arrays in das resultierende Array geschrieben und dieser Vorgang wird wiederholt, bis keine weiteren Elemente in den beiden Arrays vorhanden sind. Das heißt, wenn wir zwei minimale Arrays {6} und {4} haben , werden ihre Werte verglichen und das Ergebnis wird geschrieben: {4,6} . Wenn sortierte Arrays {4,6} und {2,8} vorhanden sind , werden zunächst die Werte 4 und 2 verglichen , von denen 2 in das resultierende Array geschrieben werden. Danach werden 4 und 8 verglichen , 4 aufgeschrieben und am Ende 6 und 8 verglichen . Dementsprechend wird 6 geschrieben und erst danach - 8. Als Ergebnis erhalten wir das resultierende Array: {2,4,6,8} . Wie wird das im Java-Code aussehen? Um diesen Algorithmus zu verarbeiten, ist es für uns praktisch, die Rekursion zu verwenden:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       testArr = mergeSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static int[] mergeSort(int[] array1) {
       int[] sortArr = Arrays.copyOf(array1, array1.length);// массив для сортировки
       int[] bufferArr = new int[array1.length];// буферный массив
       return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
           return sortArr;
       }

       // запускаем рекурсию, чтобы получить два отсортированных массива:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Слияние отсортированных массивов:
       int firstIndex = startIndex;
       int secondIndex = middle;
       int destIndex = startIndex;
       int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
       while (firstIndex < middle && secondIndex < endIndex) {
           result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
                   ? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
       }
       while (firstIndex < middle) {
           result[destIndex++] = firstSortArr[firstIndex++];
       }
       while (secondIndex < endIndex) {
           result[destIndex++] = secondSortArr[secondIndex++];
       }
       return result;
   }
}

Wie bei der Schnellsortierung verschieben wir die rekursive Methode in eine Zwischenmethode, sodass sich der Benutzer nicht die Mühe machen muss, zusätzliche Standardargumente festzulegen, sondern einfach das Array angeben kann, das sortiert werden muss. Da dieser Algorithmus einem schnelleren Löschen ähnelt, ist seine Ausführungsgeschwindigkeit dieselbe – O(N*logN) .

2. Gierige Algorithmen

Ein Greedy-Algorithmus ist ein Ansatz, der in jeder Phase lokal optimale Entscheidungen trifft und davon ausgeht, dass die endgültige Lösung ebenfalls optimal sein wird. Die „optimale“ Lösung ist diejenige, die in einem bestimmten Schritt/Stadium den offensichtlichsten und unmittelbarsten Nutzen bietet. Um diesen Algorithmus zu betrachten, wählen wir ein ziemlich häufiges Problem aus – etwa einen Rucksack. Stellen wir uns für eine Sekunde vor, Sie wären ein Dieb. Du bist nachts mit einem Rucksack in ein Geschäft eingebrochen und vor dir liegen eine Menge Waren, die du stehlen kannst. Allerdings ist das Fassungsvermögen des Rucksacks begrenzt – nicht mehr als 30 herkömmliche Einheiten. Gleichzeitig möchten Sie möglichst viele Waren mitnehmen, die in Ihren Rucksack passen. Wie entscheiden Sie, was Sie einfüllen? Der Greedy-Algorithmus für das Rucksackproblem besteht also aus den folgenden Schritten (wir gehen davon aus, dass alle Objekte in den Rucksack passen):

1. Wählen Sie den teuersten Artikel aus den noch nicht berührten Artikeln aus.
2. Wenn es in Ihren Rucksack passt, legen Sie es dort ab. Wenn nicht, lassen Sie es weg.
3. Haben Sie alle Artikel sortiert? Wenn nicht, kehren wir zu Punkt 1 zurück, wenn ja, rennen wir aus dem Laden, da unser Ziel hier erreicht ist.

Schauen wir uns das an, aber in Java. So sieht die Item-Klasse aus:

public class Item implements Comparable<Item> {
   private String name;
   private int weight;
   private int cost;

   public Item(String name, int weight, int cost) {
       this.name = name;
       this.weight = weight;
       this.cost = cost;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getCost() {
       return cost;
   }

   @Override
   public int compareTo(Item o) {
       return this.cost > o.cost ? -1 : 1;
   }
}

Hier gibt es nichts Besonderes: drei Felder – Name , Gewicht , Kosten – zur Angabe der Eigenschaften des Artikels. Wie Sie sehen können, ist hier auch die Comparable- Schnittstelle implementiert , damit wir unsere Artikel nach Preis sortieren können. Als nächstes schauen wir uns die Klasse unserer Rucksack- Tasche an :

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentCost;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentCost = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentCost() {
       return currentCost;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentCost += item.getCost();
   }
}

• maxWeight ist die Kapazität unseres Rucksacks, die beim Erstellen des Objekts festgelegt wird;
• Gegenstände – Gegenstände im Rucksack;
• currentWeight , currentCost – das aktuelle Gewicht und die aktuellen Kosten aller Dinge im Rucksack, die wir erhöhen, wenn wir in der Methode addItem einen neuen Artikel hinzufügen .

Gehen wir eigentlich zu der Klasse, in der die ganze Action stattfindet:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("гитара",7, 800));
       items.add(new Item("утюг",6, 500));
       items.add(new Item("чайник",3, 300));
       items.add(new Item("лампа",4, 500));
       items.add(new Item("телевизор",15, 2000));
       items.add(new Item("ваза",2, 450));
       items.add(new Item("миксер",1, 400));
       items.add(new Item("блендер",3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
               ", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
}

Zuerst erstellen wir eine Liste von Elementen und sortieren sie. Erstellen Sie ein Taschenobjekt mit einer Kapazität von 30 Einheiten. Als nächstes senden wir die Elemente und das Bag-Objekt an die fillBackpack- Methode , bei der der Rucksack tatsächlich mit einem Greedy-Algorithmus gefüllt wird:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

Alles ist ganz einfach: Wir beginnen, die Liste der Artikel nach Kosten sortiert durchzugehen und sie in eine Tüte zu packen, sofern die Kapazität dies zulässt. Wenn dies nicht möglich ist, wird das Element übersprungen und der Durchgang durch die verbleibenden Elemente wird bis zum Ende der Liste fortgesetzt. Durch Ausführen von main erhalten wir die folgende Ausgabe auf der Konsole: Tatsächlich ist dies ein Beispiel für einen Greedy-Algorithmus: Bei jedem Schritt wird eine lokal optimale Lösung ausgewählt, und am Ende erhält man eine global optimale Lösung. In unserem Fall ist die beste Option der teuerste Artikel. Aber ist das die beste Lösung? Glauben Sie nicht, dass wir unsere Lösung ein wenig modernisieren könnten, um einen Rucksack mit höheren Gesamtkosten auszustatten? Schauen wir uns an, wie das geht:

public static void effectiveFillBackpack(Bag bag, List<Item> items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getCost() / item.getWeight(), item);
   }

   for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
           bag.addItem(entry.getValue());
       }
   }
}

Hier berechnen wir zunächst für jeden Artikel das Gewichts-Preis-Verhältnis. Wie viel kostet sozusagen eine Einheit eines bestimmten Artikels? Und nach diesen Werten sortieren wir unsere Artikel und legen sie in unsere Tasche. Lass uns laufen:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

Wir erhalten die Ausgabe auf der Konsole: Ein bisschen besser, nicht wahr? Ein Greedy-Algorithmus trifft bei jedem Schritt eine lokal optimale Wahl mit der Erwartung, dass die endgültige Lösung ebenfalls optimal ist. Dies ist nicht immer gerechtfertigt, aber für viele Probleme bieten Greedy-Algorithmen ein Optimum. Die zeitliche Komplexität dieses Algorithmus beträgt O(N) , was ziemlich gut ist, oder? Damit ist der erste Teil dieses Artikels zu Ende. Wenn Sie an der Fortsetzung dieses Artikels interessiert sind, in dem es um Diagramme und damit verbundene Algorithmen geht, finden Sie ihn hier .