Müsahibədə soruşduqları şey: alqoritmlərin nəzərdən keçirilməsi, 1-ci hissə

Hər kəsə günortan xeyir! Layihələrdə düşündüyünüzdən daha tez-tez müxtəlif növ alqoritmlərdən istifadə olunur. Məsələn, bəzi məlumatları müəyyən parametrlərə (sütunlara) görə çeşidləməliyik ki, çox səy göstərmədən oradan keçə bilək. Buna görə də qəribə heç nə yoxdur ki, iş müsahibələri zamanı onlardan bu və ya digər əsas alqoritm haqqında sual oluna bilər və ola bilsin ki, koddan istifadə edərək onu həyata keçirmək tapşırığı verilə bilər. Siz bu saytda olduğunuz üçün Java-da yazdığınızı təxmin etməyə cəsarət edərdim. Buna görə də, bu gün sizi bəzi əsas alqoritmlər və onların Java-da həyata keçirilməsinin konkret nümunələri ilə tanış olmağa dəvət edirəm. Bəziləri ilə deyirəm:

1. Massiv çeşidləmə alqoritmlərinə ümumi baxış:
   • qabarcıq çeşidi,
   • seçim çeşidi,
   • daxil etmə çeşidi,
   • Qabıq çeşidi,
   • sürətli çeşidləmə,
   • birləşmə çeşidi.
2. Acgöz alqoritm.
3. Yol tapmaq alqoritmləri:
   • dərinlikdə sürünür
   • geniş tarama.
4. Nəqliyyat alqoritmi Dijkstra alqoritmidir.

Yaxşı, uzatmadan, işə başlayaq.

1. Çeşidləmə alqoritmlərinə ümumi baxış

Bubble çeşidi

Bu çeşidləmə alqoritmi ilk növbədə sadəliyi ilə tanınır, lakin o, həm də ən aşağı icra sürətlərindən birinə malikdir. Nümunə olaraq, artan qaydada nömrələr üçün qabarcıq sıralamasını nəzərdən keçirin. Zəncirin əvvəlindən başlayaraq aşağıdakı addımların yerinə yetiriləcəyi təsadüfi yerləşdirilmiş nömrələr zəncirini təsəvvür edək:

• iki ədədi müqayisə edin;
• soldakı nömrə daha böyükdürsə, onları dəyişdirin;
• bir mövqe sağa köçürün.

Bütün zənciri keçdikdən və bu addımları yerinə yetirdikdən sonra ən böyük rəqəmin nömrələr seriyamızın sonunda olduğunu görəcəyik. Sonra, yuxarıda təsvir olunan addımlardan sonra zəncir boyunca eyni keçid həyata keçirilir. Amma bu dəfə siyahının sonuncu elementini daxil etməyəcəyik, çünki o, ən böyüyüdür və olması lazım olduğu kimi artıq sonuncu yerdədir. Yenə sözügedən nömrələr seriyamızın sonunda sonuncu elementi alacağıq. Müvafiq olaraq, iki ən böyük rəqəm artıq öz yerlərində olacaq. Və yenidən bütün elementlər lazımi qaydada olana qədər artıq mövcud olan elementlər istisna olmaqla, zəncir boyunca keçid başlayır. Java kodunda qabarcıq çeşidləmənin tətbiqinə baxaq:

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ördüyünüz kimi, burada mürəkkəb bir şey yoxdur və hər şey əla görünür, əgər bir “amma” olmasaydı... Bubble çeşidləmə çox, çox yavaşdır, O(N²) zaman mürəkkəbliyi ilə , çünki biz yuva qurmuşuq. ilmələr. Elementlərdən xarici keçid N dəfə yerinə yetirilir, daxili də N dəfədir və nəticədə N*N , N² iterasiyaları əldə edirik.Bu cür çeşidləməni bu məqalədə daha ətraflı öyrənə bilərsiniz .

Seçimlə çeşidləmə

Bu alqoritm qabarcıq sıralamasına bənzəyir, lakin bir az daha sürətli işləyir. Yenə də misal olaraq artan ardıcıllıqla düzmək istədiyimiz bir sıra ədədləri götürək. Alqoritmin mahiyyəti ardıcıl olaraq bütün nömrələri keçmək və ən kiçik elementi seçmək və götürüb yerlərini ən sol elementlə (0 element) dəyişdirməkdir. Burada qabarcıq sıralamasına bənzər bir vəziyyət əldə edirik, lakin bu halda çeşidlənmiş element ən kiçik olacaq. Beləliklə, elementlər arasından növbəti keçid 1-ci indeksdəki elementlə başlayacaq. Yenə də bütün elementlər sıralanana qədər bu keçidlər təkrarlanacaq. Java-da tətbiq:

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 alqoritm qabarcıq sortundan üstündür, çünki burada lazımi dəyişdirmələrin sayı O(N²)-dən O(N)-ə endirilir: biz bir elementi bütün siyahı boyunca itələmirik, lakin buna baxmayaraq, müqayisələrin sayı O(N²) olaraq qalır. ) . Bu alqoritm haqqında daha çox öyrənmək istəyənlər üçün bu materialı tövsiyə edirəm .

Daxiletmə çeşidi

Bir daha misal olaraq, artan ardıcıllıqla düzmək istədiyimiz bir sıra ədədləri götürək. Bu alqoritm bir marker yerləşdirməkdən ibarətdir, onun solunda elementlər artıq öz aralarında qismən sıralanacaq. Alqoritmin hər addımında elementlərdən biri seçiləcək və artıq çeşidlənmiş ardıcıllıqla istədiyiniz mövqeyə yerləşdiriləcək. Beləliklə, çeşidlənmiş hissə bütün elementlərə baxılana qədər böyüməyə davam edəcək. Soruşa bilərsiniz: elementlərin artıq çeşidlənmiş və bundan sonra marker qoymaq lazım olan hissəsini haradan əldə edə bilərəm? Ancaq birinci elementin massivi artıq çeşidlənib, elə deyilmi? Java-da tətbiqə baxaq:

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 növ çeşidləmə yuxarıda təsvir edilənlərdən daha üstündür, çünki işləmə müddətinin eyni olmasına baxmayaraq - O(N²) , bu alqoritm qabarcıq sortundan iki dəfə və seçim çeşidindən bir qədər sürətli işləyir. Ətraflı burada oxuyun .

Qabıq çeşidi

Bu növ, təbiətinə görə dəyişdirilmiş əlavə sortudur. Mən nədən danışıram? Gəlin qaydada gedək. Bir addım seçilir və bu seçim üçün bir çox yanaşma var. Bu məsələ ilə bağlı çox təfərrüata girməyəcəyik. Massivimizi yarıya bölək və müəyyən bir rəqəm əldə edək - bu bizim addımımız olacaq. Beləliklə, massivdə 9 elementimiz varsa , addımımız 9/2 = 4.5 olacaq . Massiv indeksləri yalnız tam ədədlər olduğu üçün kəsr hissəsini atırıq və 4 alırıq. Bu addımla qruplarımız üçün əlaqələr yaradacağıq. Əgər element 0 indeksinə malikdirsə, onun qrupundakı növbəti elementin indeksi 0+4 , yəni 4- dür . Üçüncü elementin indeksi 4+4 , dördüncünün indeksi 8+4 və s. olacaq. İkinci qrup üçün birinci element 1,5,9… olacaq. Üçüncü və dördüncü qruplarda işlər tam olaraq eyni olacaq. Nəticədə {6,3,8,8,6,9,4,11,1} ədədlər massivindən dörd qrup alırıq: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Onlar ümumi massivdə öz yerlərini saxlayırlar, lakin bizim üçün onlar eyni qrupun üzvləri kimi qeyd olunur: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Daha sonra bu qruplar daxilində yuxarıda təsvir edilmiş əlavə çeşidi , bundan sonra qruplar belə görünəcək: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Ümumi massivdə qrupların tutduğu xanalar eyni qalacaq, lakin onların daxilindəki sıra yuxarıdakı qrupların sırasına uyğun olaraq dəyişəcək: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Massiv bir az daha ardıcıldır, elə deyilmi? Növbəti addım 2-yə bölünəcək: 4/2 = 2 İki qrupumuz var: I - {1,4,6,8,6} II - {3,8,9,11} B ümumi massivi: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Daxiletmə çeşidləmə alqoritmindən istifadə edərək hər iki qrupdan keçirik və massiv alırıq: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} İndi massivimiz demək olar ki, çeşidlənib. Alqoritmin son iterasiyası qalır: addımı 2-yə bölürük: 2/2 = 1. Qrup, bütün massivi alırıq: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } By hansı ki, biz daxiletmə çeşidləmə alqoritmindən keçib : { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Bu çeşidləməni Java kodunda necə göstərə biləcəyimizi görək:

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; // уменьшаем наш шаг
       }
   }
}

Hal-hazırda, Shell çeşidlənməsinin effektivliyi həqiqətən əsaslandırılmır, çünki nəticələr müxtəlif vəziyyətlərdə fərqlənir. Təcrübələrdən alınan təxminlər O(N ^3/2 ) ilə O(N ^7/6 ) arasında dəyişir .

Tez çeşidləmə

Bu ən məşhur alqoritmlərdən biridir və buna görə də xüsusi diqqət yetirməyə dəyər. Bu alqoritmin mahiyyəti ondan ibarətdir ki, elementlər siyahısından pivot element seçilir - əsasən qalan dəyərlərin çeşidlənməsi lazım olan hər hansı bir element. Solda ondan kiçik dəyərlər, sağda olduğundan daha böyük dəyərlər. Sonra, sağ və sol hissələr də dəstəkləyici element tərəfindən seçilir və eyni şey baş verir: dəyərlər bu elementlərə nisbətən sıralanır, sonra dəstəkləyici elementlər yaranan hissələrdən seçilir - və biz çeşidlənənə qədər. sıra. Java-da bu alqoritm rekursiyadan istifadə etməklə həyata keçirilir:

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

Şübhəsiz ki, sürətli çeşidləmə alqoritmi ən populyar hesab olunur, çünki əksər hallarda O(N*logN) vaxtında digərlərindən daha sürətli işləyir .

Birləşdirmə çeşidi

Bu çeşidləmə də məşhurdur. Bu, "böl və qalib gəl" prinsipi ilə işləyən alqoritm növlərindən birinə aiddir: onlarda əvvəlcə tapşırıqları minimal hissələrə bölürük ( sürətli çeşidləmə də belə alqoritmlərin nümayəndəsidir ). Yaxşı, bu alqoritmin mahiyyəti nədir?

Paylaş:

Massiv təxminən eyni ölçülü iki hissəyə bölünür, bu iki hissənin hər biri daha ikiyə bölünür və ən kiçik bölünməz hissələr qalana qədər belə davam edir. Hər massivin bir elementi olduqda ən az bölünməyən hissələr olur, yəni belə massiv avtomatik olaraq çeşidlənmiş sayılır.

Fəth etmək:

Burada alqoritmə ad verən proses başlayır - birləşmə . Bunu etmək üçün, nəticədə iki sıralı massiv götürün və onları birinə birləşdirin. Bu zaman iki massivin ilk elementlərindən ən kiçiyi yaranan massivə yazılır və bu əməliyyat iki massivdə artıq element qalmayana qədər təkrarlanır. Yəni iki minimum {6} və {4} massivimiz varsa , onların dəyərləri müqayisə ediləcək və nəticə yazılacaq: {4,6} . Əgər {4,6} və {2,8} sıralanmış massivlər varsa , əvvəlcə 4 və 2 dəyəri müqayisə ediləcək , onlardan 2- si nəticədə yaranan massivə yazılacaqdır. Bundan sonra 4 və 8 müqayisə ediləcək , 4 yazılacaq və sonunda 6 və 8 müqayisə ediləcək . Müvafiq olaraq, 6 yazılacaq və yalnız ondan sonra - 8. Nəticə olaraq, əldə edilən massivi alacağıq: {2,4,6,8} . Bu Java kodunda necə görünəcək? Bu alqoritmi emal etmək üçün rekursiyadan istifadə etmək bizim üçün əlverişli olacaq:

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

Sürətli çeşidləmədə olduğu kimi, biz rekursiv metodu ara üsula keçirik ki, istifadəçi əlavə defolt arqumentlər təyin etməklə narahat olmasın, sadəcə olaraq çeşidlənməsi lazım olan massivi təyin edə bilsin. Bu alqoritm daha sürətli silməyə bənzədiyindən onun icra sürəti eynidir - O(N*logN) .

2. Acgöz alqoritmlər

Acgöz alqoritm hər mərhələdə yerli olaraq optimal qərarlar qəbul edən və son həllin də optimal olacağını güman edən bir yanaşmadır. “Optimal” həll müəyyən addım/mərhələdə ən bariz və dərhal fayda təklif edən həlldir. Bu alqoritmi nəzərdən keçirmək üçün kifayət qədər ümumi bir problem seçəcəyik - bir sırt çantası haqqında. Gəlin bir anlıq elə bil ki, sən oğrusan. Gecə bir çanta ilə mağazaya girdin və qarşında oğurlaya biləcəyin bir sıra mallar var. Ancaq eyni zamanda, kürək çantasının tutumu məhduddur - 30 şərti vahiddən çox deyil. Eyni zamanda, bel çantanıza sığacaq maksimum dəyərə malik mal dəstini daşımaq istəyirsiniz. Nə qoyacağınıza necə qərar verirsiniz? Beləliklə, çanta probleminin acgöz alqoritmi aşağıdakı addımlardan ibarətdir (biz bütün obyektlərin çantaya uyğun olduğunu güman edirik):

1. Hələ toxunmayanlardan ən bahalı əşyanı seçin.
2. Sırt çantanıza sığarsa, oraya qoyun, yoxsa, atlayın.
3. Bütün maddələri sıralamısınız? Yoxdursa, 1-ci nöqtəyə qayıdırıq, əgər varsa, mağazadan qaçırıq, çünki burada məqsədimiz tamamlandı.

Gəlin buna baxaq, amma Java-da. Item sinfi belə görünəcək:

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

Burada xüsusi bir şey yoxdur: üç sahə - ad , çəki , qiymət - maddənin xüsusiyyətlərini göstərmək üçün. Həmçinin, gördüyünüz kimi, Müqayisəli interfeys burada həyata keçirilir ki, biz Əşyalarımızı qiymətə görə çeşidləyə bilək. Sonra çantamızın sinfinə baxırıq - Çanta :

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 obyekti yaratarkən təyin olunan kürək çantamızın tutumudur;
• əşyalar — kürək çantasındakı əşyalar;
• cariWeight , currentCost - addItem metodunda yeni bir maddə əlavə edərkən artırdığımız kürək çantasındakı hər şeyin cari çəkisi və dəyəri .

Əslində, bütün hərəkətlərin baş verdiyi sinifə gedək:

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

Əvvəlcə elementlərin siyahısını yaradırıq və onu sıralayırıq. 30 ədəd tutumlu çanta obyekti yaradın. Sonra elementləri və çanta obyektini fillBackpack metoduna göndəririk ki, burada əslində sırt çantası tamah alqoritmi ilə doldurulur:

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

Hər şey olduqca sadədir: biz qiymətə görə çeşidlənmiş əşyaların siyahısını nəzərdən keçirməyə başlayırıq və imkan verirsə, onları çantaya qoyuruq. İmkan vermirsə, element atlanacaq və qalan elementlərdən keçid siyahının sonuna qədər davam edəcək. Main-i işlətməklə, konsola aşağıdakı çıxışı alırıq: Əslində, bu, acgöz alqoritmin nümunəsidir: hər addımda lokal optimal həll seçilir və sonda siz qlobal miqyasda optimal həll əldə edirsiniz. Bizim vəziyyətimizdə ən yaxşı seçim ən bahalı maddədir. Ancaq bu ən yaxşı həll yoludurmu? Sizə elə gəlmirmi ki, biz öz həllimizi bir az modernləşdirə bildik ki, kürək çantasını daha yüksək ümumi xərclə təchiz edək? Bunun necə edilə biləcəyinə nəzər salaq:

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

Burada əvvəlcə hər bir maddə üçün çəki-qiymət nisbətini hesablayırıq. Belə desək, müəyyən bir maddənin bir vahidi nə qədərdir? Və bu dəyərlərə görə əşyalarımızı çeşidləyib çantamıza əlavə edirik. Gəl qaçaq:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

Çıxışı konsola alırıq: Bir az daha yaxşı, elə deyilmi? Açgözlü bir alqoritm, son həllin də optimal olacağını gözləməklə, hər addımda yerli olaraq optimal seçim edir. Bu, həmişə əsaslandırılmır, lakin bir çox problemlər üçün acgöz alqoritmlər optimaldır. Bu alqoritmin vaxt mürəkkəbliyi O(N) -dir , bu olduqca yaxşıdır, elə deyilmi? Beləliklə, məqalənin birinci hissəsi başa çatdı. Onlarla əlaqəli qrafiklər və alqoritmlər haqqında danışacaq bu məqalənin davamı ilə maraqlanırsınızsa, burada tapa bilərsiniz .