Алар интервьюда эмнени сурашат: алгоритмдерди карап чыгуу, 1-бөлүк

Баарыңарга кутман кеч! Алгоритмдердин ар кандай түрлөрү долбоорлордо сиз ойлогондон да көп колдонулат. Мисалы, кээ бир маалыматтарды белгилүү бир параметрлерге (мамычаларга) ылайык иргешибиз керек, андыктан көп күч-аракет жумшабастан, алар аркылуу өтүшүбүз керек. Ошондуктан, жумуш маектеринде алардан тигил же бул негизги алгоритм жөнүндө суралышы мүмкүн, балким, codeду колдонуу менен аны ишке ашыруу тапшырмасы берorшинде таң калыштуу эч нерсе жок. Жана сиз бул сайтта болгондуктан, мен сиз Java тorнде жазасыз деп ойлогум келет. Ошондуктан, бүгүн мен сизди кээ бир негизги алгоритмдер жана аларды Java тorнде ишке ашыруунун конкреттүү мисалдары менен таанышууга чакырам. Кээ бирлери менен мен:

1. Массивдерди сорттоо алгоритмдерине сереп салуу:
   • көбүк сорту,
   • тандоо сорту,
   • киргизүү сорту,
   • кабык сорту,
   • тез сорттоо,
   • бириктирүү сорту.
2. Ач көз алгоритм.
3. Жол табуу алгоритмдери:
   • терең сойлоп
   • кең сойлоо.
4. Транспорт алгоритми – бул Дийкстранын алгоритми.

Мейли, көпкө созулбай, ишке киришели.

1. Сорттоо алгоритмдерине сереп салуу

Көбүктү сорттоо

Бул сорттоо алгоритми биринчи кезекте өзүнүн жөнөкөйлүгү менен белгилүү, бирок ал эң төмөнкү аткаруу ылдамдыктарынын бирине да ээ. Мисал катары, көбөйүү тартибинде сандар үчүн көбүк иреттөөнү карап көрөлү. Келгиле, тизмектин башынан баштап төмөнкү кадамдар аткарыла турган туш келди жайгаштырылган сандар чынжырын элестетип көрөлү:

• эки санды салыштыруу;
• сол жактагы сан чоңураак болсо, анда аларды алмаштырыңыз;
• бир позицияны оңго жылдыруу.

Бүт чынжырдан өтүп, бул кадамдарды аткаргандан кийин, эң чоң сан биздин сандар катарыбыздын аягында экенин көрөбүз. Андан кийин, жогоруда сүрөттөлгөн кадамдарды аткарып, чынжыр боюнча дал ушундай өтүү жүргүзүлөт. Бирок бул жолу биз тизменин акыркы элементин киргизбейбиз, анткени ал эң чоң жана эң акыркы орунда, ошондой болушу керек. Дагы, биз каралып жаткан сандар сериясынын аягындагы акыркы элементти алабыз. Демек, эң чоң эки сан өз ордунда болот. Жана бардык элементтер талап кылынган тартипте болмоюнча, мурунтан эле орун алган элементтерди кошпогондо, чынжыр боюнча өтүү башталат. Келгиле, 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;
             }
         }
       }
   }
}

Көрүнүп тургандай, бул жерде эч кандай татаал эч нерсе жок жана баары сонун көрүнөт, эгер бир “бирок” болбосо... Көбүктү сорттоо өтө, өтө жай, убакыт татаалдыгы 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²) , бул алгоритм көбүктүү сорттон эки эсе тез жана тандоо сортунан бир аз ылдамыраак иштейт. Кененирээк бул жерден окуңуз .

Shell сорттоо

Бул сорт өзүнүн табияты боюнча өзгөртүлгөн киргизүү түрү болуп саналат. Мен эмне жөнүндө айтып жатам? Тартип менен кетели. Кадам тандалды жана бул тандоого көптөгөн ыкмалар бар. Биз бул маселе боюнча өтө майда-чүйдөсүнө чейин барбайбыз. Массивибизди экиге бөлүп, белгилүү бир санды алалы - бул биздин кадамыбыз болот. Ошентип, массивде 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 } Андан ары бул топтордун ичинде жогоруда сүрөттөлгөн киргизүү сорту , андан кийин топтор төмөнкүдөй болот: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Жалпы массивде топтор ээлеген уячалар ошол эле бойдон калат, бирок алардын ичиндеги тартип жогорудагы топтордун тартибине ылайык өзгөрөт: { 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 } By Биз киргизүүнүн сорттоо алгоритминен өтүп, төмөнкүнү алабыз: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Келгиле, бул сорттоону 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; // уменьшаем наш шаг
       }
   }
}

Азыркы учурда Shell сорттоосунун эффективдүүлүгү чындыгында далилденген эмес, анткени натыйжалар ар кандай кырдаалдарда айырмаланат. Эксперименттерден алынган баа O(N ^3/2 ) дан O(N ^7/6 ) га чейин .

Тез сорттоо

Бул эң популярдуу алгоритмдердин бири, ошондуктан ага өзгөчө көңүл буруу зарыл. Бул алгоритмдин маңызы элементтердин тизмесинен пивот элементи тандалып алынат - негизинен калган баалуулуктарды иргеп чыгуу керек болгон каалаган элемент. Андан азыраак маанилер сол жакта, андан чоңураактар ​​оң жакта. Андан кийин, оң жана сол бөлүктөрү да колдоочу элемент тарабынан тандалып алынат жана ошол эле нерсе болот: баалуулуктар бул элементтерге салыштырмалуу иреттелет, андан кийин колдоо элементтери алынган бөлүктөрдөн тандалып алынат - жана биз сорттолгонго чейин уланат. катар. Java тorндеги бул алгоритм рекурсияны колдонуу менен ишке ашырылат:

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} . Бул Java codeунда кандай болот? Бул алгоритмди иштетүү үчүн бизге рекурсияны колдонуу ыңгайлуу болот:

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. Ач көздүк алгоритмдери

Ач көз алгоритм ар бир этапта жергorктүү оптималдуу чечимдерди кабыл алган жана акыркы чечим да оптималдуу болот деп эсептеген ыкма. "Оптималдуу" чечим - бул белгилүү бир кадамда/этапта эң айкын жана дароо пайданы сунуш кылган чечим. Бул алгоритмди карап чыгуу үчүн, биз кеңири таралган маселени тандап алабыз - рюкзак жөнүндө. Келгиле, сен уурусуң деп бир азга түртүп көрөлү. Түнкүсүн рюкзак менен дүкөнгө кирдиңиз, алдыңызда уурдап кете турган бир топ товарлар турат. Бирок, ошол эле учурда, рюкзак кубаттуулугу чектелген - 30 шарттуу бирдиктерден ашык эмес. Ошол эле учурда, сиз рюкзактарыңызга бата турган максималдуу баадагы товарлардын топтомун алып жүрүүнү каалайсыз. Эмнени салууну кантип чечесиз? Ошентип, сумка маселесинин ач көз алгоритми төмөнкү кадамдардан турат (бардык an objectилер сумкага туура келет деп ойлойбуз):

1. Колу тийе электердин ичинен эң кымбат буюмду тандаңыз.
2. Эгер рюкзакыңызга туура келсе, аны ошол жерге салыңыз, эгер жок болсо, өткөрүп жибериңиз.
3. Бардык нерселерди иреттеп көрдүңүзбү? Болбосо, биз 1-пунктка кайтабыз, ооба болсо, дүкөндөн качабыз, анткени бул жерде биздин максатыбыз аткарылды.

Муну карап көрөлү, бирок Java тorнде. 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исин түзүү. Андан кийин, биз элементтерди жана баштык 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);
       }
   }
}

Баары өтө жөнөкөй: биз баасына жараша тизмеден өтүп, мүмкүнчүлүк болсо, аларды баштыкка сала баштайбыз. Эгер ал жол бербесе, элемент өткөрүп жиберилет жана калган элементтерден өтүү тизменин аягына чейин уланат. Негизги иштетүү менен, биз консолго төмөнкү натыйжаны алабыз: Чынында, бул ач көз алгоритмдин мисалы: ар бир кадамда локалдык оптималдуу чечим тандалып алынат, акырында сиз глобалдык оптималдуу чечимге ээ болосуз. Биздин учурда эң жакшы вариант эң кымбат нерсе. Бирок бул эң жакшы чечимби? Сиздин оюңузча, биз өзүбүздүн чечимибизди бир аз модернизациялап, рюкзактарды жалпы баасы жогорураак жабдый алабыз деп ойлобойсузбу? Келгиле, муну кантип жасоого болорун карап көрөлү:

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) болуп саналат , бул абдан жакшы, туурабы? Ошентип, бул макаланын биринчи бөлүгү аяктады. Сиз аларга байланыштуу графиктер жана алгоритмдер жөнүндө сөз болот, бул макаланын уландысы кызыкдар болсо, бул жерден таба аласыз .