Söhbetdeşlikde soraýan zatlary: algoritmlere syn, 1-nji bölüm

Günüňiz haýyrly bolsun! Taslamalarda dürli algoritmler siziň pikir edişiňizden has ýygy ulanylýar. Mysal üçin, köp zähmet çekmezden geçip bilmek üçin käbir maglumatlary belli bir parametrlere (sütünlere) görä tertipleşdirmeli. Şol sebäpden, iş söhbetdeşliklerinde olardan bir ýa-da başga bir esasy algoritm barada soralyp bilinjekdigi we belki kod ulanyp durmuşa geçirmek meselesi berlendigi geň zat däl. Bu sahypada bolanyňyz üçin, Java-da ýazýandygyňyzy çaklamak isleýärin. Şonuň üçin, bu gün sizi käbir esasy algoritmler we Java-da durmuşa geçirmegiň anyk mysallary bilen tanyşmaga çagyrýaryn. Käbirleri göz öňünde tutýaryn:

1. Toplumlary tertipleşdirmek algoritmlerine syn:
   • köpürjik görnüşi,
   • saýlama görnüşi,
   • goýmak görnüşi,
   • Gabyk görnüşi,
   • çalt sortlamak,
   • görnüşi birleşdirmek.
2. Açgöz algoritm.
3. Pathfinding algoritmleri:
   • çuňlukda süýrenmek
   • giň gezelenç.
4. Ulag algoritmi Dijkstranyň algoritmidir.

Bolýar, goşmaça sözlemiz, geliň, işe gireliň.

1. Sorting algoritmlerine syn

Köpürjik görnüşi

Bu sortlaşdyryş algoritmi, esasan, ýönekeýligi bilen tanalýar, ýöne şol bir wagtyň özünde iň pes ýerine ýetiriş tizligine eýe. Mysal üçin, sanlar üçin köpelýän tertipde köpürjik görnüşini göz öňünde tutuň. Geliň, tötänleýin ýerleşdirilen sanlaryň zynjyryny göz öňüne getireliň, zynjyryň başyndan başlap aşakdaky ädimler ýerine ýetiriler:

• iki san deňeşdiriň;
• çep tarapdaky san has köp bolsa, olary çalyşyň;
• bir pozisiýany saga geçiriň.

Tutuş zynjyry gözden geçirip, bu ädimleri ýerine ýetirenimizden soň, iň köp sanyň sanlarymyzyň ahyrynda bolandygyny göreris. Ondan soň, ýokarda görkezilen ädimleri ýerine ýetirip, zynjyryň boýundaky edil şol bir geçiş ýerine ýetirilýär. Thisöne bu gezek sanawyň soňky elementini goşmarys, sebäbi iň ulusy we bolşy ýaly eýýäm iň soňky ýerde. Againene-de soralýan sanlar tapgyrymyzyň ahyrynda iň soňky elementi alarys. Şoňa laýyklykda iň uly iki san eýýäm öz ýerlerinde bolar. Againene-de ähli elementler zerur tertipde bolýança, eýýäm bar bolan elementleri hasaba almazdan, zynjyryň boýundaky geçiş başlaýar. Java kodunda köpürjik görnüşiniň ýerine ýetirilişine seredeliň:

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;
             }
         }
       }
   }
}

Görşüňiz ýaly, bu ýerde çylşyrymly zat ýok we bir "ýöne" üçin däl bolsa, hemme zat gaty gowy ýaly ... Köpürjik görnüşi, höwürtgesimizden bäri O (N²) wagt çylşyrymlylygy bilen gaty haýal. aýlawlar. Elementleriň üsti bilen daşarky geçiş N gezek ýerine ýetirilýär, içki bölegi hem N gezek bolýar we netijede N * N , N² gaýtalamalaryny alýarys. Bu görnüşi sortlamagy bu makalada has jikme-jik öwrenip bilersiňiz .

Saýlama boýunça tertiplemek

Bu algoritm köpürjik görnüşine meňzeýär, ýöne birneme çalt işleýär. Againene-de bir mysal hökmünde, ýokarlanýan tertipde tertiplemek isleýän sanlarymyzyň bir toparyny alalyň. Algoritmiň düýp manysy, ähli sanlardan yzygiderli geçmek we iň çep elementi (0 element) bilen ýerleri çalyşmak we iň kiçi elementi saýlamakdyr. Bu ýerde köpürjik görnüşine meňzeş bir ýagdaý alýarys, ýöne bu ýagdaýda sortlanan element iň kiçi bolar. Şonuň üçin elementleriň indiki geçişi 1-nji indeksdäki element bilen başlar. Againene-de bu geçişler ähli elementler tertiplenýänçä gaýtalanar. Java-da ýerine ýetiriş:

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;
       }
   }
}

Bu algoritm köpürjik görnüşinden has ýokarydyr, sebäbi bu ýerde zerur permutasiýalaryň sany O (N²) -den O (N) -e çenli azalýar: bir elementi tutuş sanawdan basmaýarys, ýöne muňa garamazdan, deňeşdirmeleriň sany O (N²) bolup galýar ) . Bu algoritm hakda has giňişleýin öwrenmek isleýänler üçin bu materialy maslahat berýärin .

Goýmagyň görnüşi

Againene-de bir mysal hökmünde, ýokarlanýan tertipde tertiplemek isleýän sanlarymyzyň bir toparyny alalyň. Bu algoritm, çep tarapda elementler eýýäm öz aralarynda bölekleýin tertipleşdiriljek marker goýmakdan ybaratdyr. Algoritmiň her ädiminde elementleriň biri saýlanar we eýýäm tertiplenen yzygiderlilikde islenýän ýere ýerleşdiriler. Şeýlelik bilen tertiplenen bölek, ähli elementlere seredilýänçä ösmegini dowam etdirer. Sorap bilersiňiz: elementleriň eýýäm tertiplenen we soňundan bellik goýmaly bölegini nireden alyp bilerin? Emma birinji elementiň massiwi eýýäm tertiplenen, şeýlemi? Java-da durmuşa geçirilişine seredeliň:

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;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Bu sortlaşdyrma görnüşi ýokarda görkezilenlerden has ýokarydyr, sebäbi işleýiş wagtynyň birmeňzeşdigine garamazdan - O (N²) , bu algoritm köpürjik görnüşinden iki esse çalt we saýlama görnüşinden birneme çalt işleýär. Has giňişleýin okaň .

Gabyk görnüşi

Bu görnüş, tebigaty boýunça üýtgedilen goýmak görnüşidir. Men näme hakda gürleşýärin? Geliň, tertipli gideliň. Bir ädim saýlandy we bu saýlamaga köp çemeleşmeler bar. Bu meselä gaty jikme-jik girmeris. Geliň, massiwimizi iki bölege bölüp, belli bir san alalyň - bu biziň ädimimiz bolar. Şeýlelik bilen, massiwde 9 element bar bolsa , ädimimiz 9/2 = 4.5 bolar . Bölek böleklerini taşlaýarys we 4 alýarys , sebäbi massiw görkezijileri diňe bitewi san. Bu ädim bilen toparlarymyz üçin baglanyşyk dörederis. Bir elementiň 0 görkezijisi bar bolsa, toparyndaky indiki elementiň görkezijisi 0 + 4 , ýagny 4 . Üçünji elementde 4 + 4 indeks , dördünjide 8 + 4 indeks bolar we ş.m. Ikinji topar üçin birinji element 1,5,9 bolar ... Üçünji we dördünji toparlarda zatlar edil birmeňzeş bolar. Netijede, {6,3,8,8,6,9,4,11,1 numbers sanlar toplumyndan dört topar alýarys: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Olar umumy tertipde öz ýerlerini saklaýarlar, ýöne biziň üçin şol bir toparyň agzalary hökmünde bellendi: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Mundan başga-da bu toparlaryň içinde ýokarda beýan edilen goşma görnüşi , şondan soň toparlar şeýle bolar: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 , 11} Umumy massiwde, toparlaryň eýeleýän öýjükleri öňküligine galar, ýöne ýokardaky toparlaryň tertibine görä içindäki tertip üýtgär: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 ay Bu massiw birneme tertipli, şeýlemi? Indiki ädim 2: 4/2 = 2 bölüner: Bizde iki topar bar: I - {1,4,6,8,6} II - {3,8,9,11} B umumy massiw: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Goýma sort algoritmini ulanyp, iki topara geçýäris we bir massiw alýarys: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Indi biziň massiwimiz tertiplenen diýen ýaly. Algoritmiň iň soňky gaýtalanmagy galýar: ädimi 2: 2/2 = 1-e bölýäris. 1. Topar, tutuş massiw alarys: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } goýmak sort algoritminden geçýäris we alarys: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Geliň, bu tertibi Java kodunda nädip görkezip biljekdigimizi göreliň:

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]) {//sorting вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

Häzirki wagtda “Shell” sortlamagyň täsiri hakykatdanam subut edilmeýär, sebäbi netijeler dürli ýagdaýlarda tapawutlanýar. Synaglardan alnan çaklamalar O (N ^3/2 ) -den O (N ^7/6 ) aralygynda .

Çalt görnüş

Bu iň meşhur algoritmleriň biridir, şonuň üçin aýratyn üns bermelidiris. Bu algoritmiň düýp manysy, esasy elementleriň sanawyndan saýlanylmagydyr, esasanam galan bahalary tertipleşdirmeli islendik element. Çep tarapdakydan az bahalar, sagdakydan has uly bahalar. Ondan soň, sag we çep bölekler hem goldaýan element tarapyndan saýlanýar we şol bir zat bolýar: bahalar bu elementlere görä tertiplenýär, soňra goldaýan elementler emele gelen böleklerden saýlanýar - we ş.m. hatar. Java-daky bu algoritm gaýtalanma arkaly amala aşyrylýar:

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)// condition выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так How нечего уже делить
           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);
   }
}

Şübhesiz, çalt algoritm iň meşhur hasaplanýar, sebäbi köp ýagdaýlarda O (N * logN) wagtynda beýlekilerden has çalt işleýär .

Birleşdiriň

Bu sortlamak hem meşhurdyr. "Bölmek we basyp almak" ýörelgesinde işleýän algoritmleriň bir görnüşine degişlidir: olarda ilki bilen meseleleri minimal böleklere bölýäris ( çalt sortlamak hem şeýle algoritmleriň wekili ). Onda bu algoritmiň manysy näme?

Bölün:

Bu massiw takmynan deň ölçegdäki iki bölege bölünýär, bu iki bölekiň her biri ýene iki bölege bölünýär we iň kiçi bölünmeýän bölekler galýança we ş.m. Iň az bölünmeýän bölekler, her massiwde bir element bar bolsa, şeýle massiw awtomatiki tertiplenen hasaplanýar.

Queňiji:

Algoritmiň adyny birleşdirýän - birleşýän ýer şu ýerden başlaýar . Munuň üçin iki sany sargyt edilen massiw alyň we olary birleşdiriň. Bu ýagdaýda, iki massiwiň ilkinji elementleriniň iň kiçisi emele gelen massiwde ýazylýar we bu amal iki massiwde başga elementler bolýança gaýtalanýar. .Agny, iki sany minimal massiw {6} we {4} bar bolsa , olaryň bahalary deňeşdiriler we netije ýazylar: {4,6} . {4,6} we {2,8 sort tertipli massiwler bar bolsa , ilki bilen 4 we 2 bahasy deňeşdiriler , şolardan 2-si netijäniň massiwine ýazylar. Ondan soň 4 we 8 deňeşdiriler , 4-si ýazylar we ahyrynda 6 we 8-ler deňeşdiriler . Şoňa laýyklykda 6 ýazylar we diňe şondan soň - 8. Netijede, netijäni alarys: {2,4,6,8} . Java kodunda bu nähili görüner? Bu algoritmi gaýtadan işlemek üçin gaýtalanmagy ulanmak amatly bolar:

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;
   }
}

Çalt tertipde bolşy ýaly, ulanyjy goşmaça deslapky argumentleri düzmekden biynjalyk bolmazlygy üçin, diňe tertipleşdirilmeli massiwini görkezip biler ýaly, gaýtalanýan usuly aralyk usulyna geçirýäris. Bu algoritm has çalt pozulmaga meňzeş bolany üçin, ýerine ýetiriş tizligi birmeňzeş - O (N * logN) .

2. Açgöz algoritmler

Açgöz algoritm , her etapda ýerli optimal kararlary kabul edýän we gutarnykly çözgüdiň hem optimal boljakdygyny çaklaýan çemeleşme. “Iň amatly” çözgüt, belli bir ädimde / etapda iň aýdyň we derrew peýdany hödürleýän çözgütdir. Bu algoritmi göz öňünde tutmak üçin, adaty bir meseläni - sumka hakda saýlarys. Özüňizi ogry diýip bir sekuntlap ​​görkezeliň. Gije sumka bilen dükana girdiň, öňüňde ogurlap boljak birnäçe haryt bar. Theöne şol bir wagtyň özünde, sumkanyň kuwwaty çäklidir - adaty birlik 30-dan köp bolmaly däldir. Şol bir wagtyň özünde, sumkaňyza laýyk boljak iň ýokary bahasy bolan harytlar toplumyny götermek isleýärsiňiz. Nämä salmalydygyny nädip çözmeli? Şeýlelik bilen, aç-açan problema üçin açgöz algoritm aşakdaky ädimlerden durýar (ähli obýektleriň pese gaçýandygyny çaklaýarys):

1. Entek degilmediklerden iň gymmat zady saýlaň.
2. Eger sumkaňyza gabat gelýän bolsa, ony şol ýere goýuň, ýok bolsa, ony atyň.
3. Thehli zatlary tertiplediňizmi? Notok bolsa, 1-nji punkta gaýdyp gelýäris, hawa bolsa, dükandan gaçýarys, sebäbi bu ýerdäki maksadymyz tamamlandy.

Geliň, muňa seredeliň, ýöne Java-da. Haryt synpynyň görnüşi:

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;
   }
}

Bu ýerde üýtgeşik zat ýok: elementiň aýratynlyklaryny kesgitlemek üçin üç meýdan - ady , agramy , bahasy . Şeýle hem, görşüňiz ýaly, Harytlarymyzy baha boýunça tertipläp bilmek üçin Deňeşdirilýän interfeýs bu ýerde amala aşyrylýar. Soň bolsa sumkamyzyň synpyna seredýäris - Torba :

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 , obýekt döredilende düzülen sumkamyzyň kuwwatydyr;
• zatlar - sumkadaky zatlar;
• currentWeight , currentCost - sumkadaky ähli zatlaryň häzirki agramy we bahasy, addItem usulyna täze element goşanymyzda köpelýäris .

Aslynda, ähli hereketleriň bolup geçýän synpyna geçeliň:

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

Ilki bilen elementleriň sanawyny döredýäris we tertipleşdirýäris. 30 birlik göwrümli sumka obýektini dörediň. Ondan soň, elementleri we sumka obýektini fillBackpack usulyna iberýäris , aslynda sumka açgöz algoritm bilen doldurylýar:

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

Hemme zat diýseň ýönekeý: gymmaty boýunça tertiplenen zatlaryň sanawyndan geçip, mümkinçilikler bar bolsa sumka salýarys. Rugsat bermese, element atlanar we galan elementlerden geçiş sanawyň ahyryna çenli dowam eder. Esasy işlemek bilen, konsola aşakdaky çykyşy alýarys: Aslynda bu açgöz algoritmiň mysaly: her ädimde ýerli optimal çözgüt saýlanýar we ahyrynda global derejede optimal çözgüt alarsyňyz. Biziň ýagdaýymyzda iň gowy wariant iň gymmat zat. Emma bu iň gowy çözgütmi? Çantany has umumy çykdajy bilen enjamlaşdyryp biler ýaly çözgüdimizi azajyk döwrebaplaşdyryp bileris öýdemok? Muny nädip edip boljakdygyna göz aýlalyň:

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

Bu ýerde ilki bilen her elementiň agram bahasyny hasaplaýarys. Diýmek, berlen elementiň bir birligi näçe? Bu gymmatlyklar boýunça zatlarymyzy tertipläp, sumkamyza goşýarys. Geliň:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

Çykyşy konsola alýarys: Biraz gowy, şeýlemi? Açgöz algoritm, soňky çözgüdiň hem optimal boljakdygyna umyt edip, her ädimde ýerli derejede optimal saýlaýar. Bu elmydama dogry däl, ýöne köp meseleler üçin açgöz algoritmler optimal üpjün edýär. Bu algoritmiň wagt çylşyrymlylygy O (N) , gaty gowy, şeýlemi? Dogrusy, bu makalanyň birinji bölümi tamamlandy. Grafikler we olar bilen baglanyşykly algoritmler barada gürleşjek bu makalanyň dowamy bilen gyzyklanýan bolsaňyz, şu ýerden tapyp bilersiňiz .