Он чизе ки онҳо дар мусоҳиба мепурсанд: баррасии алгоритмҳо, қисми 1

Нимаи хуб ба ҳама! Намудҳои гуногуни алгоритмҳо дар лоиҳаҳо бештар аз он ки шумо фикр мекунед, истифода мешаванд. Масалан, мо бояд баъзе маълумотҳоро аз рӯи параметрҳои (сутунҳои) муайян ҷудо кунем, то мо бе кӯшиши зиёд тавассути он ҳаракат кунем. Аз ин рӯ, ҳеҷ чизи аҷибе нест, ки ҳангоми мусоҳибаҳои корӣ аз онҳо дар бораи ин ё он алгоритми асосӣ пурсидан мумкин аст ва шояд вазифаи татбиқи он бо истифода аз code дода шавад. Ва азбаски шумо дар ин сайт ҳастед, ман мехостам тахмин кунам, ки шумо дар Java менависед. Аз ин рӯ, имрӯз ман шуморо даъват мекунам, ки бо баъзе алгоритмҳои асосӣ ва мисолҳои мушаххаси татбиқи онҳо дар Java шинос шавед. Бо баъзеҳо ман дар назар дорам:

1. Баррасии алгоритмҳои ҷудокунии массив:
   • навъҳои ҳубобӣ,
   • навъ интихоб,
   • навъ дохил кардан,
   • Навъи ҷилди,
   • навъҳои зуд,
   • навъ муттаҳид.
2. Алгоритми пурқувват.
3. Алгоритмҳои ҷустуҷӯ:
   • дар амиқ хазандагон
   • сайри васеъ.
4. Алгоритми интиқол алгоритми Дижкстра мебошад.

Хуб, бе гапи дигар, биёед ба кор гузарем.

1. Баррасии алгоритмҳои ҷудокунӣ

Навъи ҳубобӣ

Ин алгоритми ҷудокунӣ пеш аз ҳама бо соддагии худ маълум аст, аммо дар айни замон вай яке аз пасттарин суръати иҷроро дорад. Ҳамчун мисол, ҷудокунии ҳубобӣ барои рақамҳоро бо тартиби афзоиш баррасӣ кунед. Биёед як занҷири рақамҳои ба таври тасодуфӣ ҷойгиршударо тасаввур кунем, ки барои онҳо қадамҳои зерин аз ибтидои занҷир иҷро карда мешаванд:

• ду рақамро муқоиса кунед;
• агар шумораи дар тарафи чап калонтар бошад, пас онҳоро иваз кунед;
• як мавқеъ ба рост ҳаракат кунед.

Пас аз гузаштани тамоми занҷир ва иҷрои ин қадамҳо, мо мефаҳмем, ки шумораи калонтарин дар охири силсилаи рақамҳои мост. Минбаъд, маҳз ҳамон гузариш дар баробари занҷир, пас аз қадамҳои дар боло тавсифшуда иҷро карда мешавад. Аммо ин дафъа мо унсури охирини рӯйхатро дохил намекунем, зеро он бузургтарин аст ва аллакай дар ҷои охирин аст, тавре ки бояд бошад. Боз, мо унсури охиринро дар охири силсилаи рақамҳои мавриди назар мегирем. Мутаносибан, ду рақами калонтарин аллакай дар ҷойҳои худ хоҳанд буд. Ва боз гузаргоҳ дар баробари занҷир оғоз мешавад, ба истиснои унсурҳое, ки аллакай ҷойгиранд, то он даме, ки ҳамаи элементҳо дар тартиби зарурӣ бошанд. Биёед ба татбиқи навъбандии ҳубобӣ дар codeи Java назар андозем:

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

Тавре ки шумо мебинед, дар ин ҷо ҳеҷ чизи мураккаб нест ва ҳама чиз олиҷаноб ба назар мерасад, агар барои як "аммо" набошад... Навъи ҳубобӣ хеле ва хеле суст аст, бо мураккабии вақти O (N²) , зеро мо лона гузоштаем ҳалқаҳо. Гузариши беруна аз элементҳо дар N маротиба, дарунӣ низ N маротиба анҷом дода мешавад ва дар натиҷа мо такрори N*N , N² ба даст меорем.Шумо метавонед ин навъи ҷудокуниро дар ин мақола муфассалтар омӯзед .

Ҷудокунӣ аз рӯи интихоб

Ин алгоритм ба навъбандии ҳубобӣ монанд аст, аммо он каме тезтар кор мекунад. Боз ҳам, ҳамчун мисол, биёед як қатор рақамҳоро гирем, ки мо мехоҳем бо тартиби афзоиш ҷойгир кунем. Мохияти алгоритм ин аст, ки пай дар пай аз тамоми ракамхо гузашта, элементи хурдтаринеро интихоб кунем, ки мо онро гирифта, чойхоро бо элементи чапи аз хама (элемент 0) иваз мекунем. Дар ин ҷо мо вазъиятеро ба даст меорем, ки ба навъбандии ҳубобӣ монанд аст, аммо дар ин ҳолат унсури мураттабшуда хурдтарин хоҳад буд. Аз ин рӯ, гузариши навбатӣ аз элементҳо аз элементи индекси 1 оғоз мешавад. Боз ин гузаришҳо то ба тартиб андохта шудани ҳамаи элементҳо такрор карда мешаванд. Татбиқ дар 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;
       }
   }
}

Ин алгоритм аз навъбандии ҳубобӣ бартарӣ дорад, зеро дар ин ҷо шумораи ивазкуниҳои зарурӣ аз O(N²) ба O(N) кам карда мешавад: мо як элементро дар тамоми рӯйхат пахш намекунем, аммо бо вуҷуди ин, шумораи муқоисаҳо O(N²) боқӣ мемонад. ) . Барои онҳое, ки мехоҳанд дар бораи ин алгоритм маълумоти бештар гиранд, ман ин маводро тавсия медиҳам .

Навъи воридкунӣ

Бори дигар, ҳамчун мисол, биёед як қатор рақамҳоро гирем, ки мо мехоҳем бо тартиби афзоиш ҷойгир кунем. Ин алгоритм аз гузоштани маркер иборат аст, ки дар тарафи чапи он элементҳо аллакай қисман байни худ ҷудо карда мешаванд. Дар ҳар як қадами алгоритм яке аз элементҳо интихоб карда мешавад ва дар мавқеи дилхоҳ дар пайдарпаии аллакай мураттабшуда ҷойгир карда мешавад. Ҳамин тавр, қисми ҷудошуда то он даме, ки ҳамаи унсурҳо дида нашаванд, афзоиш хоҳад ёфт. Шумо метавонед бипурсед: ман метавонам он қисми элементҳоеро, ки аллакай мураттаб шудаанд, аз куҷо гирам ва пас аз он ба шумо маркер гузоштан лозим аст? Аммо массиви элементи аввал аллакай мураттаб шудааст, ҳамин тавр не? Биёед ба татбиқи Java назар андозем:

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

Ин навъи навъбандӣ нисбат ба навъҳои дар боло тавсифшуда бартарӣ дорад, зеро сарфи назар аз он, ки вақти кор яксон аст - O(N²) , ин алгоритм нисбат ба навъбандии ҳубобӣ ду маротиба тезтар ва аз навъбандии интихоб каме тезтар кор мекунад. Муфассалтар дар ин ҷо бихонед .

Навъи қабз

Ин навъ, аз рӯи табиати худ, як навъи воридкунии тағирёфта мебошад. Ман дар бораи чӣ гап мезанам? Биёед бо тартиб равем. Қадам интихоб карда мешавад ва ба ин интихоб равишҳои зиёде мавҷуданд. Мо ба ин масъала чандон муфассал намеравем. Биёед массивамонро ба ду тақсим кунем ва рақами муайянро ба даст орем - ин қадами мо хоҳад буд. Пас, агар мо дар массив 9 элемент дошта бошем, пас қадами мо 9/2 = 4,5 хоҳад буд . Мо қисми касрро партофта, 4 мегирем , зеро индексҳои массив танҳо ададҳои бутун мебошанд. Бо ин қадам мо барои гурӯҳҳои худ робита эҷод мекунем. Агар элемент индекси 0 дошта бошад, пас индекси элементи навбатии гурӯҳи он 0+4 аст , яъне 4 . Элементи сеюм дорои индекси 4+4 , чорум индекси 8+4 ва ғайра мебошад. Барои гурӯҳи дуюм, унсури якум 1,5,9…. Дар гурУххои сейум ва чорум хам кор айнан хамин хел мешавад. Дар натиҷа, аз массиви ададҳои {6,3,8,8,6,9,4,11,1} чор гурӯҳ мегирем: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Онҳо ҷойҳои худро дар массиви умумӣ нигоҳ медоранд, аммо барои мо онҳо ҳамчун аъзои як гурӯҳ қайд карда мешаванд: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Минбаъд дар дохor ин гурӯҳҳо навъбандии , ки баъд аз он гурӯҳҳо чунин хоҳанд буд: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Дар массиви умумӣ ячейкаҳое, ки гурӯҳҳо ишғол кардаанд, бетағйир боқӣ мемонанд, аммо тартиби дохor онҳо мувофиқи тартиби гурӯҳҳои дар боло зикршуда тағир меёбад: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Массив каме бештар тартиб дода шудааст, ҳамин тавр не? Қадами навбатӣ ба 2 тақсим мешавад: 4/2 = 2 Мо ду гурӯҳ дорем: I - {1,4,6,8,6} II - {3,8,9,11} B массиви умумӣ: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Мо бо истифода аз алгоритми навъбандии ворид ҳарду гурӯҳро мегузарем ва массив мегирем: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Холо массивамон кариб ба тартиб оварда шудааст. Итератсияи охирини алгоритм боқӣ мемонад: қадамро ба 2 тақсим мекунем: 2/2 = 1. Мо як гурӯҳ, тамоми массивро мегирем: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Бо ки мо аз алгоритми навъбандии воридкунӣ мегузарем ва ба даст меорем: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Биёед бубинем, ки чӣ тавр мо ин навъбандиро дар codeи Java намоиш дода метавонем:

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

Дар айни замон, самаранокии навъбандии Shell воқеан тасдиқ карда нашудааст, зеро натиҷаҳо дар ҳолатҳои гуногун фарқ мекунанд. Ҳисобҳои аз таҷрибаҳо гирифташуда аз O(N ^3/2 ) то O(N ^7/6 ) мебошанд .

Навъи зуд

Ин яке аз алгоритмҳои маъмултарин аст ва аз ин рӯ ба он диққати махсус додан лозим аст. Моҳияти ин алгоритм дар он аст, ки як унсури даврӣ аз рӯйхати элементҳо интихоб карда мешавад - аслан ҳама гуна унсуре, ки бар зидди он арзишҳои боқимонда бояд мураттаб карда шаванд. Қиматҳои камтар аз он дар тарафи чап, арзишҳо бузургтар аз он дар тарафи рост. Баъдан, қисмҳои рост ва чап низ аз ҷониби унсури дастгирӣ интихоб карда мешаванд ва ҳамин чиз рӯй медиҳад: арзишҳо нисбат ба ин элементҳо мураттаб карда мешаванд, пас унсурҳои дастгирӣ аз қисмҳои натиҷавӣ интихоб карда мешаванд - ва ғайра то он даме, ки мо мураттаб карда шавем. қатор. Ин алгоритм дар Java бо истифода аз рекурсия амалӣ карда мешавад:

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

Бешубҳа, алгоритми навъбандии фаврӣ маъмултарин ҳисобида мешавад, зеро дар аксари ҳолатҳо он дар вақти O(N*logN) нисбат ба дигарон тезтар кор мекунад .

Навъи якҷоякунӣ

Ин навъбандӣ низ маъмул аст. Он ба яке аз навъҳои алгоритмҳое дахл дорад, ки аз рӯи принсипи “тақсим кун ва ғалаба кун” кор мекунанд: дар онҳо мо пеш аз ҳама вазифаҳоро ба қисмҳои минималӣ тақсим мекунем ( ҷабрдидаи зуд низ намояндаи чунин алгоритмҳост ). Пас, моҳияти ин алгоритм чист?

Мубодила:

Массив ба ду қисмҳои тақрибан якхела тақсим карда мешавад, ҳар яке аз ин ду қисм ба дуи дигар тақсим мешавад ва ҳамин тавр то он даме, ки хурдтарин қисмҳои тақсимнашаванда боқӣ монад. Қисмҳои камтарин тақсимнашаванда вақте мебошанд, ки ҳар як массив як элемент дорад, яъне чунин массив ба таври худкор мураттабшуда ҳисобида мешавад.

Ғалаба:

Дар ин ҷо раванде оғоз мешавад, ки номи алгоритмро медиҳад - merging . Барои ин, ду массиви тартибдодашударо гиред ва онҳоро ба як муттаҳид кунед. Дар ин ҳолат хурдтарини элементҳои аввалини ду массив ба массиви натиҷавӣ навишта мешавад ва ин амал то он даме, ки дар ду массив дигар элементҳо мавҷуд набошанд, такрор карда мешаванд. Яъне, агар мо ду массиви минималии {6} ва {4} дошта бошем , арзишҳои онҳо муқоиса карда мешаванд ва натиҷа навишта мешавад: {4,6} . Агар массивҳои мураттабшуда {4,6} ва {2,8} мавҷуд бошанд , аввал қимати 4 ва 2 муқоиса карда мешавад , ки аз он 2 ба массиви натиҷавӣ навишта мешавад. Пас аз ин, 4 ва 8 муқоиса карда мешаванд , 4 навишта мешаванд ва дар охир 6 ва 8 муқоиса карда мешаванд . Мутаносибан, 6 навишта мешавад ва танҳо пас аз он - 8. Дар натиҷа массиви натиҷавӣ ба даст меояд: {2,4,6,8} . Ин дар codeи Java чӣ гуна хоҳад буд? Барои коркарди ин алгоритм, истифодаи рекурсия барои мо қулай хоҳад буд:

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

Тавре ки дар навъбандии зуд, мо усули рекурсивиро ба усули мобайнӣ интиқол медиҳем, то корбар набояд бо муқаррар кардани аргументҳои пешфарзии иловагӣ ташвиш кашад, балки танҳо массиверо, ки бояд мураттаб карда шавад, муайян кунад. Азбаски ин алгоритм ба тозакунии тезтар шабоҳат дорад, суръати иҷрои он яксон аст - O(N*logN) .

2. Алгоритмҳои хасис

Алгоритми хасис равишест, ки дар ҳар марҳила қарорҳои оптималии маҳаллӣ қабул мекунад ва тахмин мекунад, ки ҳалли ниҳоӣ низ оптималӣ хоҳад буд. Ҳалли "беҳтарин" ҳамонест, ки дар як қадам/марҳилаи муайян фоидаи аёнтарин ва фаврӣ пешкаш мекунад. Барои баррасии ин алгоритм, мо як масъалаи хеле маъмулро интихоб мекунем - дар бораи ҷузвдон. Биёед, як сония вонамуд кунем, ки шумо дуздед. Шумо шабона бо сумка ба магоза даромадед ва дар пешатон як катор молхое хастанд, ки онхоро дуздида метавонед. Аммо дар айни замон, иқтидори ҷузвдон маҳдуд аст - на бештар аз 30 адад муқаррарӣ. Дар айни замон, шумо мехоҳед, ки маҷмӯи молҳоро бо арзиши ҳадди аксар, ки ба ҷузвдони шумо мувофиқат мекунанд, кашед. Чӣ тавр шумо қарор медиҳед, ки чӣ гузоред? Ҳамин тавр, алгоритми тамаъкорӣ барои ҳалли масъалаи халта аз қадамҳои зерин иборат аст (мо гумон мекунем, ки ҳама an objectҳо ба сумка мувофиқанд):

1. Аз онҳое, ки ҳанӯз даст наёфтаанд, гаронтарин ашёро интихоб кунед.
2. Агар он ба ҷузвдони шумо мувофиқат кунад, онро ба он ҷо гузоред, агар не, онро гузаред.
3. Оё шумо ҳамаи ашёҳоро ҷудо кардаед? Агар не, мо ба банди 1 бармегардем, агар ҳа, аз мағоза медавидем, зеро ҳадафи мо дар ин ҷо анҷом ёфт.

Биёед инро бубинем, аммо дар Java. Синфи Item чунин хоҳад буд:

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

Дар ин ҷо ягон чизи махсус вуҷуд надорад: се майдон - ном , вазн , арзиш - барои муайян кардани хусусиятҳои ашё. Инчунин, тавре ки мебинед, интерфейси муқоисашаванда дар ин ҷо татбиқ карда мешавад , то мо метавонем ашёи худро аз рӯи нарх ҷудо кунем. Минбаъд мо ба синфи ҷузвдони худ назар мекунем - халта :

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 иқтидори ҷузвдони мост, ки ҳангоми сохтани an object муқаррар карда мешавад;
• ашё — ашё дар борхалта;
• currentWeight , currentCost - вазн ва арзиши ҷории ҳама чизҳо дар ҷузвдон, ки мо ҳангоми илова кардани ашёи нав дар усули addItem зиёд мекунем .

Дар асл, биёед ба синфе равем, ки дар он ҳама амалҳо рӯй медиҳанд:

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

Аввалан, мо рӯйхати элементҳоро эҷод мекунем ва онро ҷудо мекунем. Объекти халтаро бо иқтидори 30 адад созед. Баъдан, мо элементҳо ва an objectи халтаро ба усули fillBackpack мефиристем , ки дар он воқеан ҷузвдон бо истифода аз алгоритми хасис пур карда мешавад:

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

Ҳама чиз бениҳоят содда аст: мо ба гузаштани рӯйхати ашёҳо аз рӯи нарх ҷудо карда, онҳоро дар халта мегузорем, агар иқтидор имкон диҳад. Агар он иҷозат надиҳад, элемент гузаронида мешавад ва гузариш аз унсурҳои боқимонда то охири рӯйхат идома меёбад. Бо иҷро кардани main, мо баромади зеринро ба консол мегирем: Дар асл, ин як мисоли алгоритми тамаъкор аст: дар ҳар як қадам ҳалли оптималии маҳаллӣ интихоб карда мешавад ва дар ниҳоят шумо ҳалли беҳтарини умумиҷаҳонӣ мегиред. Дар ҳолати мо, беҳтарин вариант ашёи гаронбаҳост. Аммо оё ин роҳи беҳтарин аст? Оё шумо фикр намекунед, ки мо метавонем ҳалли худро каме навсозӣ кунем, то як ҷузвдони бо арзиши бештари умумӣ муҷаҳҳаз карда шавад? Биёед бубинем, ки чӣ тавр ин корро кардан мумкин аст:

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

Дар ин ҷо мо аввал таносуби вазн ва нархро барои ҳар як ашё ҳисоб мекунем. Агар гуем, як вохиди ашёи додашуда чанд сум аст? Ва аз рӯи ин арзишҳо мо ашёҳои худро ҷудо карда, ба сумкаамон илова мекунем. Биёед давем:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

Мо натиҷаро ба консол мегирем: Каме беҳтар, ҳамин тавр не? Алгоритми чашмгуруснагӣ дар ҳар як қадам интихоби оптималии маҳаллиро месозад ва интизор меравад, ки ҳалли ниҳоӣ низ оптималӣ хоҳад буд. Ин на ҳамеша асоснок аст, аммо барои бисёр мушкилот алгоритмҳои хасис беҳтаринро таъмин мекунанд. Мушкorи вақти ин алгоритм O(N) аст , ки хеле хуб аст, дуруст? Хуб, бо ҳамин қисми аввали ин мақола ба охир расид. Агар шумо ба идомаи ин мақола таваҷҷӯҳ дошта бошед, ки дар бораи графикҳо ва алгоритмҳои марбут ба онҳо сӯҳбат хоҳад кард, шумо метавонед онро дар ин ҷо пайдо кунед .