Ano ang itatanong nila sa isang panayam: pagsusuri ng mga algorithm, bahagi 1

Magandang hapon sa lahat! Ang iba't ibang uri ng mga algorithm ay ginagamit sa mga proyekto nang mas madalas kaysa sa iniisip mo. Halimbawa, kailangan nating pag-uri-uriin ang ilang data ayon sa ilang mga parameter (column) para makapag-navigate tayo dito nang walang labis na pagsisikap. Samakatuwid, walang kakaiba sa katotohanan na sa panahon ng mga panayam sa trabaho maaari silang tanungin tungkol sa isa o isa pang pangunahing algorithm, at marahil ay binigyan ng gawain ng pagpapatupad nito gamit ang code. At dahil ikaw ay nasa site na ito, gusto kong hulaan na sumulat ka sa Java. Samakatuwid, ngayon inaanyayahan kita na maging pamilyar sa ilang mga pangunahing algorithm at mga tiyak na halimbawa ng kanilang pagpapatupad sa Java. Sa ilan ang ibig kong sabihin:

1. Pangkalahatang-ideya ng mga algorithm ng pag-uuri ng array:
   • pag-uuri ng bula,
   • uri ng pagpili,
   • insertion sort,
   • Pag-uuri ng shell,
   • mabilis na pag-uuri,
   • sumanib-uuri.
2. Sakim na algorithm.
3. Mga algorithm sa paghahanap ng landas:
   • gumagapang sa lalim
   • malawak na lakad.
4. Ang algorithm ng transportasyon ay algorithm ng Dijkstra.

Buweno, nang walang karagdagang ado, bumaba tayo sa negosyo.

1. Pangkalahatang-ideya ng mga algorithm ng pag-uuri

Bubble sort

Ang algorithm ng pag-uuri na ito ay kilala lalo na sa pagiging simple nito, ngunit mayroon din itong isa sa pinakamababang bilis ng pagpapatupad. Bilang halimbawa, isaalang-alang ang bubble sort para sa mga numero sa pataas na pagkakasunud-sunod. Isipin natin ang isang chain ng mga random na inilagay na numero kung saan isasagawa ang mga sumusunod na hakbang, simula sa simula ng chain:

• ihambing ang dalawang numero;
• kung ang numero sa kaliwa ay mas malaki, pagkatapos ay palitan sila;
• ilipat ang isang posisyon sa kanan.

Pagkatapos na dumaan sa buong chain at isagawa ang mga hakbang na ito, makikita natin na ang pinakamalaking bilang ay nasa dulo ng aming serye ng mga numero. Susunod, ang eksaktong parehong pass sa kahabaan ng kadena ay isinasagawa, kasunod ng mga hakbang na inilarawan sa itaas. Ngunit sa pagkakataong ito ay hindi na namin isasama ang huling elemento ng listahan, dahil ito ang pinakamalaki at nasa huling lugar na, gaya ng nararapat. Muli, makukuha namin ang huling elemento sa dulo ng aming serye ng mga numerong pinag-uusapan. Alinsunod dito, ang dalawang pinakamalaking bilang ay nasa kanilang mga lugar. At muli ang pagpasa sa kahabaan ng kadena ay nagsimula, hindi kasama ang mga elemento na nasa lugar na, hanggang sa ang lahat ng mga elemento ay nasa kinakailangang pagkakasunud-sunod. Tingnan natin ang pagpapatupad ng bubble sort sa Java code:

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

Tulad ng nakikita mo, walang kumplikado dito, at ang lahat ay tila napakahusay, kung hindi para sa isang "ngunit"... Ang pag-uuri ng bubble ay napaka, napakabagal, na may kumplikadong oras na O(N²) , dahil kami ay may nested mga loop. Ang panlabas na pagpasa sa mga elemento ay ginagawa sa N beses, ang panloob ay N beses din, at bilang resulta nakakakuha kami ng N*N , N² na mga pag-ulit. Maaari mong pag-aralan ang ganitong uri ng pag-uuri nang mas detalyado sa artikulong ito .

Pag-uuri ayon sa pagpili

Ang algorithm na ito ay katulad ng bubble sort, ngunit ito ay gumagana nang kaunti nang mas mabilis. Muli, bilang isang halimbawa, kumuha tayo ng isang serye ng mga numero na gusto nating ayusin sa pataas na pagkakasunud-sunod. Ang kakanyahan ng algorithm ay ang sunud-sunod na suriin ang lahat ng mga numero at piliin ang pinakamaliit na elemento, na kinukuha namin at pinapalitan ang mga lugar na may pinakakaliwang elemento (0 elemento). Dito makakakuha tayo ng isang sitwasyon na katulad ng bubble sort, ngunit sa kasong ito ang pinagsunod-sunod na elemento ay ang pinakamaliit. Samakatuwid, ang susunod na pagpasa sa mga elemento ay magsisimula sa elemento sa index 1. Muli, ang mga pagpasa na ito ay uulitin hanggang ang lahat ng mga elemento ay pinagbukud-bukod. Pagpapatupad sa 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;
       }
   }
}

Ang algorithm na ito ay higit na mataas sa bubble sort, dahil dito ang bilang ng mga kinakailangang permutasyon ay nababawasan mula O(N²) hanggang O(N): hindi kami nagpapatakbo ng isang elemento sa buong listahan, ngunit gayunpaman, ang bilang ng mga paghahambing ay nananatiling O(N² ) . Para sa mga nagnanais na matuto nang higit pa tungkol sa algorithm na ito, inirerekomenda ko ang materyal na ito .

Pag-uuri ng pagpapasok

Muli, bilang isang halimbawa, kumuha tayo ng isang serye ng mga numero na nais nating ayusin sa pataas na pagkakasunud-sunod. Binubuo ang algorithm na ito ng paglalagay ng marker, sa kaliwa kung saan ang mga elemento ay bahagyang pag-uuri-uriin sa kanilang mga sarili. Sa bawat hakbang ng algorithm, pipiliin ang isa sa mga elemento at ilalagay sa nais na posisyon sa nakaayos na pagkakasunod-sunod. Kaya't ang pinagsunod-sunod na bahagi ay patuloy na lalago hanggang ang lahat ng mga elemento ay matingnan. Maaari mong itanong: saan ko makukuha ang bahaging iyon ng mga elemento na pinagsunod-sunod na at pagkatapos nito kailangan mong maglagay ng marker? Ngunit ang hanay ng unang elemento ay nakaayos na, hindi ba? Tingnan natin ang pagpapatupad sa 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;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Ang ganitong uri ng pag-uuri ay mas mataas kaysa sa mga inilarawan sa itaas, dahil sa kabila ng katotohanan na ang oras ng pagpapatakbo ay pareho - O(N²) , gumagana ang algorithm na ito nang dalawang beses nang mas mabilis kaysa sa bubble sort at bahagyang mas mabilis kaysa sa selection sort. Magbasa pa dito .

Pag-uuri ng shell

Ang uri na ito, ayon sa likas na katangian nito, ay isang binagong insertion sort. Ano ba ang sinasabi ko? Umayos na tayo. Ang isang hakbang ay pinili, at mayroong maraming mga diskarte sa pagpipiliang ito. Hindi namin tatalakayin ang isyung ito nang masyadong detalyado. Hatiin natin ang ating array sa kalahati at makakuha ng isang tiyak na numero - ito ang magiging hakbang natin. Kaya, kung mayroon tayong 9 na elemento sa array, ang magiging hakbang natin ay 9/2 = 4.5 . Itapon namin ang fractional na bahagi at makakuha ng 4 , dahil ang mga indeks ng array ay mga integer lamang. Sa hakbang na ito gagawa kami ng mga koneksyon para sa aming mga grupo. Kung ang isang elemento ay may index 0, kung gayon ang index ng susunod na elemento sa pangkat nito ay 0+4 , iyon ay, 4 . Ang ikatlong elemento ay magkakaroon ng index na 4+4 , ang ikaapat ay magkakaroon ng index na 8+4 , at iba pa. Para sa pangalawang pangkat, ang unang elemento ay magiging 1,5,9…. Sa ikatlo at ikaapat na grupo, ang mga bagay ay magiging eksaktong pareho. Bilang resulta, mula sa hanay ng mga numero {6,3,8,8,6,9,4,11,1} nakakakuha tayo ng apat na grupo: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Pinananatili nila ang kanilang mga lugar sa pangkalahatang hanay, ngunit para sa amin ay minarkahan sila bilang mga miyembro ng parehong grupo: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Karagdagan sa loob ng mga pangkat na ito ang insertion sort , pagkatapos nito ang mga pangkat ay magiging ganito ang hitsura: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Sa pangkalahatang hanay, ang mga cell na inookupahan ng mga pangkat, ay mananatiling pareho, ngunit ang pagkakasunud-sunod sa loob ng mga ito ay magbabago, ayon sa pagkakasunud-sunod ng mga pangkat sa itaas: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Medyo mas maayos ang array, di ba? Ang susunod na hakbang ay hahatiin ng 2: 4/2 = 2 Mayroon kaming dalawang grupo: I - {1,4,6,8,6} II - {3,8,9,11} B general array: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Dumadaan kami sa parehong grupo gamit ang insertion sort algorithm at kumuha ng array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Ngayon ang aming array ay halos pinagsunod-sunod. Ang huling pag-ulit ng algorithm ay nananatili: hinahati namin ang hakbang sa 2: 2/2 = 1. Kumuha kami ng isang grupo, ang buong array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Sa pamamagitan ng na dumaan tayo sa insertion sort algorithm at makuha ang : { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Tingnan natin kung paano natin maipapakita ang pag-uuri na ito sa Java code:

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

Sa ngayon, ang pagiging epektibo ng pag-uuri ng Shell ay hindi talaga napatunayan, dahil ang mga resulta ay naiiba sa iba't ibang mga sitwasyon. Ang mga pagtatantya na nakuha mula sa mga eksperimento ay mula sa O(N ^3/2 ) hanggang O(N ^7/6 ) .

Mabilis na pag-uuri

Ito ay isa sa mga pinakasikat na algorithm, at samakatuwid ito ay nagkakahalaga ng pagbibigay ng espesyal na pansin. Ang kakanyahan ng algorithm na ito ay ang isang elemento ng pivot ay pinili mula sa isang listahan ng mga elemento-sa pangkalahatan ay anumang elemento kung saan ang natitirang mga halaga ay kailangang pagbukud-bukurin. Mga halagang mas mababa kaysa sa nasa kaliwa, mas malaki kaysa sa nasa kanan. Susunod, ang kanan at kaliwang bahagi ay pinili din ng sumusuportang elemento at ang parehong bagay ay nangyayari: ang mga halaga ay pinagsunod-sunod na may kaugnayan sa mga elementong ito, pagkatapos ay ang mga sumusuportang elemento ay pinili mula sa mga nagresultang bahagi - at iba pa hanggang sa makuha namin ang isang pinagsunod-sunod. hilera. Ang algorithm na ito sa Java ay ipinatupad gamit ang recursion:

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

Walang alinlangan, ang quicksort algorithm ay itinuturing na pinakasikat, dahil sa karamihan ng mga sitwasyon ay tumatakbo ito nang mas mabilis kaysa sa iba, sa oras ng O(N*logN) .

Sumanib-uuri

Ang pag-uuri na ito ay sikat din. Ito ay tumutukoy sa isa sa mga uri ng mga algorithm na gumagana sa prinsipyo ng "hatiin at lupigin": sa mga ito ay nahahati muna namin ang mga gawain sa mga kaunting bahagi ( ang mabilis na pag-uuri ay isang kinatawan din ng mga naturang algorithm ). Kaya, ano ang kakanyahan ng algorithm na ito?

Ibahagi:

Ang array ay nahahati sa dalawang bahagi na humigit-kumulang sa parehong laki, ang bawat isa sa dalawang bahaging ito ay nahahati sa dalawa pa, at iba pa hanggang sa mananatili ang pinakamaliit na hindi mahahati na bahagi. Ang pinakamaliit na hindi mahahati na bahagi ay kapag ang bawat array ay may isang elemento, na nangangahulugan na ang naturang array ay awtomatikong itinuturing na pinagsunod-sunod.

lupigin:

Dito magsisimula ang proseso na nagbibigay ng pangalan sa algorithm - merging . Upang gawin ito, kunin ang dalawang resultang ordered array at pagsamahin ang mga ito sa isa. Sa kasong ito, ang pinakamaliit sa mga unang elemento ng dalawang array ay isinusulat sa resultang array, at ang operasyong ito ay paulit-ulit hanggang sa wala nang mga elemento sa dalawang array. Iyon ay, kung mayroon tayong dalawang minimal na array {6} at {4} , ang kanilang mga halaga ay ihahambing at ang resulta ay isusulat: {4,6} . Kung may mga pinagsunod-sunod na array {4,6} at {2,8} , pagkatapos ay ihahambing muna ang value 4 at 2 , kung saan 2 ang isusulat sa resultang array. Pagkatapos nito, ihahambing ang 4 at 8 , isusulat ang 4 , at sa huli ay ihahambing ang 6 at 8 . Alinsunod dito, 6 ang isusulat, at pagkatapos lamang nito - 8. Bilang resulta, makukuha natin ang resultang array: {2,4,6,8} . Paano ito magiging hitsura sa Java code? Upang iproseso ang algorithm na ito, magiging maginhawa para sa amin na gumamit ng recursion:

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

Tulad ng sa mabilisang pag-uuri, inililipat namin ang recursive na paraan sa isang intermediate para hindi na kailangang mag-abala ng user sa pagtatakda ng mga karagdagang default na argumento, ngunit maaari lamang tukuyin ang array na kailangang ayusin. Dahil ang algorithm na ito ay katulad ng mas mabilis na pagbura, ang bilis ng pagpapatupad nito ay pareho - O(N*logN) .

2. Mga Sakim na Algorithm

Ang isang matakaw na algorithm ay isang diskarte na kumukuha ng mga lokal na pinakamainam na desisyon sa bawat yugto at ipinapalagay na ang panghuling solusyon ay magiging pinakamainam din. Ang "pinakamainam" na solusyon ay ang isa na nag-aalok ng pinaka-halata at agarang benepisyo sa isang tiyak na hakbang/yugto. Upang isaalang-alang ang algorithm na ito, pumili tayo ng isang medyo karaniwang problema - tungkol sa isang backpack. Magpanggap tayo sandali na magnanakaw ka. Pumasok ka sa isang tindahan sa gabi na may dalang backpack, at sa harap mo ay may ilang mga kalakal na maaari mong nakawin. Ngunit sa parehong oras, ang kapasidad ng backpack ay limitado - hindi hihigit sa 30 maginoo na mga yunit. Kasabay nito, gusto mong magdala ng isang hanay ng mga kalakal na may pinakamataas na halaga na babagay sa iyong backpack. Paano ka magpapasya kung ano ang ilalagay? Kaya, ang matakaw na algorithm para sa problema sa knapsack ay binubuo ng mga sumusunod na hakbang (ipinapalagay namin na ang lahat ng mga bagay ay magkasya sa knapsack):

1. Piliin ang pinakamahal na bagay mula sa mga hindi pa nagagalaw.
2. Kung kasya ito sa iyong backpack, ilagay ito doon; kung hindi, laktawan ito.
3. Naayos mo na ba ang lahat ng mga item? Kung hindi, bumalik kami sa punto 1, kung oo, tumakbo kami mula sa tindahan, dahil natapos na ang aming layunin dito.

Tingnan natin ito, ngunit sa Java. Ito ang magiging hitsura ng klase ng 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;
   }
}

Walang espesyal dito: tatlong field - pangalan , timbang , gastos - para sa pagtukoy ng mga katangian ng item. Gayundin, tulad ng nakikita mo, ipinatupad dito ang Comparable interface para mapag-uri-uriin namin ang aming Mga Item ayon sa presyo. Susunod na tinitingnan namin ang klase ng aming backpack - Bag :

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

• ang maxWeight ay ang kapasidad ng aming backpack, na nakatakda kapag lumilikha ng bagay;
• mga bagay - mga bagay sa backpack;
• currentWeight , currentCost - ang kasalukuyang timbang at halaga ng lahat ng bagay sa backpack, na dinadagdagan namin kapag nagdaragdag ng bagong item sa addItem method .

Sa totoo lang, pumunta tayo sa klase, kung saan nangyayari ang lahat ng aksyon:

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

Una, lumikha kami ng isang listahan ng mga elemento at pag-uri-uriin ito. Gumawa ng bag object na may kapasidad na 30 units. Susunod, ipinapadala namin ang mga elemento at bagay ng bag sa paraan ng fillBackpack , kung saan, sa katunayan, ang backpack ay pinupuno gamit ang isang matakaw na algorithm:

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

Ang lahat ay napaka-simple: nagsisimula kaming dumaan sa listahan ng mga item na pinagsunod-sunod ayon sa gastos at ilagay ang mga ito sa isang bag, kung pinapayagan ng kapasidad. Kung hindi ito papayagan, ang elemento ay lalaktawan at ang pagpasa sa mga natitirang elemento ay magpapatuloy hanggang sa katapusan ng listahan. Sa pamamagitan ng pagpapatakbo ng main, nakukuha namin ang sumusunod na output sa console: Sa totoo lang, ito ay isang halimbawa ng isang matakaw na algorithm: sa bawat hakbang isang lokal na pinakamainam na solusyon ay pinili, at sa huli makakakuha ka ng isang pandaigdigang pinakamainam na solusyon. Sa aming kaso, ang pinakamagandang opsyon ay ang pinakamahal na item. Ngunit ito ba ang pinakamahusay na solusyon? Hindi mo ba naisip na maaari naming gawing moderno ang aming solusyon nang kaunti upang masangkapan namin ang isang backpack na may mas mataas na kabuuang gastos? Tingnan natin kung paano ito magagawa:

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

Dito muna namin kinakalkula ang ratio ng timbang-presyo para sa bawat item. Kung sabihin, magkano ang halaga ng isang yunit ng isang partikular na item? At ayon sa mga halagang ito, pinag-uuri-uriin namin ang aming mga item at idinagdag ang mga ito sa aming bag. Tumakbo tayo:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

Nakukuha namin ang output sa console: Medyo mas maganda, di ba? Ang isang matakaw na algorithm ay gumagawa ng lokal na pinakamainam na pagpipilian sa bawat hakbang na may inaasahan na ang panghuling solusyon ay magiging pinakamainam din. Ito ay hindi palaging makatwiran, ngunit para sa maraming mga problema ang mga matakaw na algorithm ay nagbibigay ng pinakamabuting kalagayan. Ang pagiging kumplikado ng oras ng algorithm na ito ay O(N) , na medyo maganda, tama? Buweno, kasama niyan, ang unang bahagi ng artikulong ito ay natapos na. Kung interesado ka sa pagpapatuloy ng artikulong ito, na magsasalita tungkol sa mga graph at algorithm na nauugnay sa kanila, mahahanap mo ito dito .