Intervyuda nima so'rashadi: algoritmlarni ko'rib chiqish, 1-qism

Hammaga xayrli kun! Loyihalarda siz o'ylaganingizdan ko'ra ko'proq turli xil algoritmlardan foydalaniladi. Misol uchun, biz ba'zi ma'lumotlarni ma'lum parametrlar (ustunlar) bo'yicha saralashimiz kerak, shunda biz ular bo'ylab ko'p harakat qilmasdan harakat qilishimiz mumkin. Shu sababli, ish intervyularida ulardan u yoki bu asosiy algoritm haqida so'rashi va, ehtimol, kod yordamida uni amalga oshirish vazifasi berilishi mumkinligida g'alati narsa yo'q. Va siz ushbu saytda bo'lganingiz uchun Java-da yozganingizni taxmin qilishga jur'at etaman. Shuning uchun, bugun men sizni ba'zi bir asosiy algoritmlar va ularni Java-da amalga oshirishning aniq misollari bilan tanishishingizni taklif qilaman. Ba'zilar bilan aytmoqchiman:

1. Massivlarni saralash algoritmlariga umumiy nuqtai:
   • qabariqni saralash,
   • tanlash tartibi,
   • kiritish tartibi,
   • Qobiq navi,
   • tez tartiblash,
   • birlashtirish tartibi.
2. Ochko'z algoritm.
3. Yo'lni aniqlash algoritmlari:
   • chuqurlikda emaklash
   • keng suzish.
4. Tashish algoritmi Dijkstra algoritmidir.

Xo'sh, ortiqcha cho'zmasdan, keling, ishga kirishaylik.

1. Saralash algoritmlariga umumiy nuqtai

Pufakcha tartiblash

Ushbu tartiblash algoritmi birinchi navbatda soddaligi bilan mashhur, lekin ayni paytda u eng past bajarilish tezligidan biriga ega. Misol sifatida raqamlarni o'sish tartibida pufakchali tartiblashni ko'rib chiqing. Keling, tasodifiy joylashtirilgan raqamlar zanjirini tasavvur qilaylik, ular uchun zanjir boshidan boshlab quyidagi bosqichlar bajariladi:

• ikkita raqamni solishtiring;
• agar chapdagi raqam kattaroq bo'lsa, ularni almashtiring;
• bir pozitsiyani o'ngga siljiting.

Butun zanjir bo'ylab o'tib, ushbu bosqichlarni bajarganimizdan so'ng, biz eng katta raqam bizning raqamlar seriyamiz oxirida ekanligini topamiz. Keyinchalik, yuqorida tavsiflangan amallarni bajarib, zanjir bo'ylab aynan bir xil o'tish amalga oshiriladi. Ammo bu safar biz ro'yxatning oxirgi elementini kiritmaymiz, chunki u eng katta va allaqachon oxirgi o'rinda, xuddi shunday bo'lishi kerak. Shunga qaramay, biz ko'rib chiqilayotgan raqamlar seriyasining oxirida oxirgi elementni olamiz. Shunga ko'ra, ikkita eng katta raqam allaqachon o'z joylarida bo'ladi. Va yana zanjir bo'ylab o'tish boshlanadi, barcha elementlar kerakli tartibda bo'lgunga qadar, allaqachon mavjud bo'lgan elementlar bundan mustasno. Keling, Java kodida pufakchani tartiblashni amalga oshirishni ko'rib chiqaylik:

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

Ko'rib turganingizdek, bu erda hech qanday murakkab narsa yo'q va hamma narsa ajoyib ko'rinadi, agar bitta "lekin" bo'lmasa ham... Pufakcha tartiblash juda va juda sekin, vaqt murakkabligi O(N²) ga teng , chunki biz ichki joylashtirdik. halqalar. Elementlar bo'ylab tashqi o'tish N marta, ichki ham N marta amalga oshiriladi va natijada biz N*N , N² takrorlashlarni olamiz.Bu turdagi saralashni ushbu maqolada batafsilroq o'rganishingiz mumkin .

Tanlov bo'yicha saralash

Bu algoritm pufakchani saralashga o'xshaydi, lekin u biroz tezroq ishlaydi. Yana, misol tariqasida, biz o'sish tartibida joylashtirmoqchi bo'lgan bir qator raqamlarni olaylik. Algoritmning mohiyati ketma-ket barcha raqamlardan o'tish va eng kichik elementni tanlashdir, biz uni olamiz va eng chap element (0 element) bilan joylarni almashtiramiz. Bu erda biz qabariqni tartiblash bilan o'xshash vaziyatni olamiz, lekin bu holda tartiblangan element eng kichik bo'ladi. Shuning uchun elementlardan keyingi o'tish 1-indeksdagi elementdan boshlanadi. Yana bu o'tishlar barcha elementlar tartiblashtirilguncha takrorlanadi. Java-da amalga oshirish:

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 pufakchali tartiblashdan ustundir, chunki bu yerda kerakli almashtirishlar soni O(N²) dan O(N) ga kamayadi: biz butun roʻyxat boʻylab bitta elementni surmaymiz, lekin shunga qaramay, taqqoslashlar soni O(N²) boʻlib qoladi. ) . Ushbu algoritm haqida ko'proq bilmoqchi bo'lganlar uchun men ushbu materialni tavsiya qilaman .

Kiritish tartibi

Yana bir bor, misol tariqasida, biz o'sish tartibida joylashtirmoqchi bo'lgan bir qator raqamlarni olaylik. Ushbu algoritm markerni joylashtirishdan iborat bo'lib, uning chap tomonida elementlar qisman o'zaro tartiblanadi. Algoritmning har bir bosqichida elementlardan biri tanlanadi va allaqachon tartiblangan ketma-ketlikda kerakli joyga joylashtiriladi. Shunday qilib, tartiblangan qism barcha elementlar ko'rib chiqilmaguncha o'sishda davom etadi. Siz so'rashingiz mumkin: elementlarning tartiblangan qismini qayerdan olsam bo'ladi va shundan so'ng siz markerni qo'yishingiz kerak? Lekin birinchi elementning massivi allaqachon tartiblangan, shunday emasmi? Keling, Java-da amalga oshirishni ko'rib chiqaylik:

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

Ushbu turdagi saralash yuqorida tavsiflanganlardan ustundir, chunki ish vaqti bir xil bo'lishiga qaramay - O(N²) , bu algoritm pufakchali saralashdan ikki baravar tez va tanlab olishdan bir oz tezroq ishlaydi. Batafsil bu yerda oʻqing .

Shell tartiblash

Bu tur o'z tabiatiga ko'ra o'zgartirilgan qo'shish turidir. Men nima haqida gapiryapman? Keling, tartibda boraylik. Bir qadam tanlanadi va bu tanlovga ko'plab yondashuvlar mavjud. Biz bu masala bo'yicha juda ko'p tafsilotlarga to'xtalmaymiz. Keling, massivimizni yarmiga bo'linib, ma'lum bir raqamni olamiz - bu bizning qadamimiz bo'ladi. Shunday qilib, agar bizda massivda 9 ta element bo'lsa, unda bizning qadamimiz 9/2 = 4,5 bo'ladi . Biz kasr qismini olib tashlaymiz va 4 ni olamiz , chunki massiv indekslari faqat butun sonlardir. Ushbu qadam bilan biz guruhlarimiz uchun ulanishlarni yaratamiz. Agar element 0 indeksiga ega bo'lsa, u holda uning guruhidagi keyingi elementning indeksi 0+4 , ya'ni 4 ga teng . Uchinchi element 4+4 indeksiga ega bo'ladi , to'rtinchisi 8+4 indeksiga ega bo'ladi va hokazo. Ikkinchi guruh uchun birinchi element 1,5,9... bo'ladi. Uchinchi va to'rtinchi guruhlarda hammasi xuddi shunday bo'ladi. Natijada, {6,3,8,8,6,9,4,11,1} sonlar massividan to‘rtta guruhni olamiz: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Ular umumiy massivdagi oʻz joylarini saqlab qoladilar, lekin biz uchun ular bir guruh aʼzolari sifatida belgilangan: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Keyinchalik bu guruhlar ichida yuqorida tavsiflangan qo'shish tartibi , shundan so'ng guruhlar quyidagicha ko'rinadi: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Umumiy massivda guruhlar egallagan katakchalar bir xil boʻlib qoladi, lekin ularning ichidagi tartib yuqoridagi guruhlar tartibiga koʻra oʻzgaradi: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Massiv biroz tartiblangan, shunday emasmi? Keyingi qadam 2 ga bo'linadi: 4/2 = 2 Bizda ikkita guruh mavjud: I - {1,4,6,8,6} II - {3,8,9,11} B umumiy massiv: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Qoʻshishni tartiblash algoritmi yordamida ikkala guruhni ham aylanib oʻtamiz va massivni olamiz: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Endi bizning massivimiz deyarli tartiblangan. Algoritmning oxirgi iteratsiyasi qoladi: biz qadamni 2 ga bo'lamiz: 2/2 = 1. Biz guruhni, butun massivni olamiz: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } By Biz qo'shishni tartiblash algoritmidan o'tamiz va quyidagilarni olamiz: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Keling, ushbu tartiblashni Java kodida qanday ko'rsatishimiz mumkinligini ko'rib chiqamiz:

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

Ayni paytda Shell saralash samaradorligi haqiqatan ham tasdiqlanmagan, chunki natijalar turli vaziyatlarda farqlanadi. Tajribalardan olingan taxminlar O(N ^3/2 ) dan O (N ^7/6 ) gacha .

Tez tartiblash

Bu eng mashhur algoritmlardan biri va shuning uchun unga alohida e'tibor qaratish lozim. Ushbu algoritmning mohiyati shundan iboratki, elementlar ro'yxatidan pivot elementi tanlanadi - asosan qolgan qiymatlar saralanishi kerak bo'lgan har qanday element. Undan kichikroq qiymatlar chap tomonda, qiymatlar esa o'ngdagidan kattaroq. Keyinchalik, o'ng va chap qismlar ham qo'llab-quvvatlovchi element tomonidan tanlanadi va xuddi shu narsa sodir bo'ladi: qiymatlar ushbu elementlarga nisbatan tartiblanadi, so'ngra olingan qismlardan qo'llab-quvvatlovchi elementlar tanlanadi - va biz tartiblangan bo'lgunimizcha davom etadi. qator. Java-dagi ushbu algoritm rekursiya yordamida amalga oshiriladi:

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

Shubhasiz, tezkor saralash algoritmi eng ommabop hisoblanadi, chunki ko'p hollarda u O(N*logN) vaqtida boshqalarga qaraganda tezroq ishlaydi .

Birlashtirish tartibi

Ushbu saralash ham mashhur. Bu "bo'l va zabt et" tamoyili bo'yicha ishlaydigan algoritm turlaridan biriga ishora qiladi: ularda biz birinchi navbatda vazifalarni minimal qismlarga ajratamiz ( tezkor tartiblash ham bunday algoritmlarning vakili hisoblanadi ). Xo'sh, bu algoritmning mohiyati nimada?

Bo'lmoq:

Massiv taxminan bir xil o'lchamdagi ikkita qismga bo'linadi, bu ikki qismning har biri yana ikkitaga bo'linadi va shunga o'xshash eng kichik bo'linmas qismlar qolguncha davom etadi. Har bir massiv bitta elementga ega bo'lsa, eng kichik bo'linmaydigan qismlar, ya'ni bunday massiv avtomatik ravishda tartiblangan deb hisoblanadi.

G'alaba qozonish:

Bu erda algoritmga nom beradigan jarayon boshlanadi - birlashma . Buning uchun hosil bo'lgan ikkita tartiblangan massivni oling va ularni bittaga birlashtiring. Bunda ikkita massivning birinchi elementlaridan eng kichigi hosil bo‘lgan massivga yoziladi va bu amal ikki massivda elementlar qolmaguncha takrorlanadi. Ya'ni, agar bizda ikkita minimal {6} va {4} massivlari bo'lsa , ularning qiymatlari taqqoslanadi va natija yoziladi: {4,6} . Agar tartiblangan massivlar {4,6} va {2,8} bo'lsa , avval 4 va 2 qiymatlari solishtiriladi , shundan 2 tasi olingan massivga yoziladi. Shundan so'ng, 4 va 8 taqqoslanadi , 4 yoziladi va oxirida 6 va 8 taqqoslanadi . Shunga ko'ra, 6 yoziladi va faqat undan keyin - 8. Natijada, biz hosil bo'lgan massivni olamiz: {2,4,6,8} . Bu Java kodida qanday ko'rinadi? Ushbu algoritmni qayta ishlash uchun biz uchun rekursiyadan foydalanish qulay bo'ladi:

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

Tez tartiblashda bo'lgani kabi, biz rekursiv usulni oraliq usulga o'tkazamiz, shunda foydalanuvchi qo'shimcha standart argumentlarni o'rnatish bilan bezovtalanmasligi kerak, lekin shunchaki tartiblanishi kerak bo'lgan massivni belgilashi mumkin. Ushbu algoritm tezroq o'chirishga o'xshash bo'lgani uchun uning bajarilish tezligi bir xil - O(N*logN) .

2. Ochko'zlik algoritmlari

Ochko'z algoritm - bu har bir bosqichda mahalliy optimal qarorlarni qabul qiladigan va yakuniy yechim ham optimal bo'lishini taxmin qiladigan yondashuv. "Optimal" yechim ma'lum bir bosqichda/bosqichda eng aniq va darhol foyda keltiradigan yechimdir. Ushbu algoritmni ko'rib chiqish uchun biz juda keng tarqalgan muammoni tanlaymiz - xalta haqida. Keling, bir soniya o'g'ri ekaningizni ko'rsataylik. Kechasi ryukzak bilan do‘konga bostirib kirgansiz, oldingizda o‘g‘irlash mumkin bo‘lgan bir qancha tovarlar turibdi. Ammo shu bilan birga, ryukzakning sig'imi cheklangan - 30 ta an'anaviy birlikdan ko'p emas. Shu bilan birga, siz xaltangizga sig'adigan maksimal qiymatga ega bo'lgan tovarlar to'plamini olib yurishni xohlaysiz. Nimani qo'yishni qanday hal qilasiz? Shunday qilib, yukxalta muammosining ochko'z algoritmi quyidagi bosqichlardan iborat (biz barcha ob'ektlar sumkaga mos keladi deb taxmin qilamiz):

1. Hali tegmagan narsalardan eng qimmatini tanlang.
2. Agar u xaltangizga to'g'ri kelsa, uni o'sha joyga qo'ying, bo'lmasa, o'tkazib yuboring.
3. Barcha elementlarni saralab oldingizmi? Agar yo'q bo'lsa, biz 1-bandga qaytamiz, agar shunday bo'lsa, biz do'kondan yuguramiz, chunki bu erda bizning maqsadimiz tugadi.

Keling, buni ko'rib chiqaylik, lekin Java-da. Item klassi shunday ko'rinadi:

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 erda hech qanday maxsus narsa yo'q: uchta maydon - nom , vazn , narx - buyumning xususiyatlarini ko'rsatish uchun. Bundan tashqari, siz ko'rib turganingizdek, taqqoslanadigan interfeys bu erda amalga oshirilgan , shunda biz mahsulotlarimizni narx bo'yicha saralashimiz mumkin. Keyin xaltamiz sinfini ko'rib chiqamiz - sumka :

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 - bu ob'ektni yaratishda o'rnatiladigan ryukzakimizning sig'imi;
• buyumlar — xaltadagi narsalar;
• currentWeight , currentCost - ryukzakdagi barcha narsalarning joriy og'irligi va narxi, biz addItem usuliga yangi element qo'shganda ko'paytiramiz .

Keling, barcha harakatlar sodir bo'ladigan sinfga boraylik:

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

Birinchidan, biz elementlar ro'yxatini tuzamiz va uni saralaymiz. 30 birlik sig'imli sumka ob'ektini yarating. Keyinchalik, biz elementlarni va sumka ob'ektini fillBackpack usuliga yuboramiz , bunda, aslida, ryukzak ochko'z algoritm yordamida to'ldiriladi:

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

Hammasi juda oddiy: biz narxlari bo'yicha saralangan narsalar ro'yxatini ko'rib chiqishni boshlaymiz va agar imkoniyatlar imkon bersa, ularni sumkaga joylashtiramiz. Agar ruxsat bermasa, element o'tkazib yuboriladi va qolgan elementlardan o'tish ro'yxat oxirigacha davom etadi. Mainni ishga tushirish orqali biz konsolga quyidagi natijani olamiz: Aslida, bu ochko'zlik algoritmiga misol: har bir qadamda mahalliy optimal echim tanlanadi va oxirida siz global optimal echimga ega bo'lasiz. Bizning holatda, eng yaxshi variant eng qimmat narsadir. Lekin bu eng yaxshi yechimmi? Sizningcha, biz ryukzakni umumiy xarajati yuqoriroq jihozlashimiz uchun yechimimizni biroz modernizatsiya qilsak bo'lmaydimi? Keling, buni qanday qilish mumkinligini ko'rib chiqaylik:

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 erda biz birinchi navbatda har bir element uchun vazn-narx nisbatini hisoblaymiz. Shunday qilib aytganda, berilgan buyumning bir birligi qancha turadi? Va bu qadriyatlar bo'yicha biz narsalarni saralaymiz va ularni sumkamizga qo'shamiz. Keling, yuguramiz:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

Biz chiqishni konsolga olamiz: Biroz yaxshiroq, shunday emasmi? Ochko'z algoritm har bir qadamda yakuniy yechim ham maqbul bo'lishini kutish bilan mahalliy optimal tanlovni amalga oshiradi. Bu har doim ham oqlanmaydi, lekin ko'p muammolar uchun ochko'z algoritmlar optimalni ta'minlaydi. Ushbu algoritmning vaqt murakkabligi O (N) dir , bu juda yaxshi, to'g'rimi? Shunday qilib, ushbu maqolaning birinchi qismi o'z nihoyasiga yetdi. Agar siz ushbu maqolaning davomi bilan qiziqsangiz, ular bilan bog'liq grafiklar va algoritmlar haqida gapiradigan bo'lsak, uni bu erda topishingiz mumkin .