Сұхбатта не сұрайды: алгоритмдерді шолу, 1 бөлім

Қайырлы күн баршаңызға! Алгоритмдердің әртүрлі түрлері жобаларда сіз ойлағаннан да жиі пайдаланылады. Мысалы, кейбір деректерді белгілі бір параметрлерге (бағандарға) сәйкес сұрыптауымыз керек, сонда біз оны көп күш жұмсамай-ақ шарлай аламыз. Сондықтан, жұмыс сұхбаты кезінде олардан сол немесе басқа негізгі алгоритмдер туралы сұралуы мүмкін және codeты пайдаланып оны енгізу тапсырмасы берілуі мүмкін екенінде таңқаларлық ештеңе жоқ. Сіз осы сайтта болғандықтан, сіз Java тілінде жазасыз деп ойлаймын. Сондықтан бүгін мен сіздерді кейбір негізгі алгоритмдермен және оларды Java тілінде іске асырудың нақты мысалдарымен танысуға шақырамын. Кейбіреулерімен айтайын дегенім:

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²) , бұл алгоритм көпіршікті сұрыптаудан екі есе жылдам және таңдау сұрыптауынан сәл жылдамырақ жұмыс істейді. Толығырақ мына жерден оқыңыз .

Қабық сұрыптау

Бұл сұрыптау өзінің табиғаты бойынша өзгертілген кірістіру сұрыптауы болып табылады. Мен не туралы айтып отырмын? Тәртіппен барайық. Қадам таңдалды және бұл таңдаудың көптеген тәсілдері бар. Біз бұл мәселеге тым егжей-тегжейлі тоқталмаймыз. Массивімізді екіге бөліп, белгілі бір санды алайық - бұл біздің қадамымыз болады. Сонымен, егер массивте 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 } біз кірістіру сұрыптау алгоритмі арқылы өтіп, мынаны аламыз: { 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 тіліндегі бұл алгоритм рекурсия арқылы жүзеге асырылады:

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) уақытында басқаларға қарағанда жылдамырақ жұмыс істейді .

Біріктіру сұрыптауы

Бұл сұрыптау да танымал. Ол «бөліп ал және жең» принципі бойынша жұмыс істейтін алгоритм түрлерінің біріне жатады: оларда біз алдымен тапсырмаларды минималды бөліктерге бөлеміз ( жылдам сұрыптау да осындай алгоритмдердің өкілі болып табылады ). Сонымен, бұл алгоритмнің мәні неде?

Бөлу:

Массив шамамен бірдей көлемдегі екі бөлікке бөлінеді, осы екі бөліктің әрқайсысы тағы екіге бөлінеді және ең кішкентай бөлінбейтін бөліктер қалғанша осылай жалғасады. Ең аз бөлінбейтін бөліктер әрбір массивтің бір элементі болған кезде болады, яғни мұндай массив автоматты түрде сұрыпталған болып саналады.

Жеңу:

Дәл осы жерде алгоритмге атау беретін процесс басталады - біріктіру . Ол үшін алынған екі реттелген массивтерді алып, оларды бір массивке біріктіріңіз. Бұл жағдайда екі массивтің бірінші элементтерінің ең кішісі алынған массивке жазылады және бұл әрекет екі массивте артық элементтер қалмайынша қайталанады. Яғни, егер бізде {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. Ашкөздік алгоритмдері

Ашкөздік алгоритм - бұл әр кезеңде жергілікті оңтайлы шешімдерді қабылдайтын және соңғы шешім де оңтайлы болады деп болжайтын тәсіл. «Оңтайлы» шешім – бұл белгілі бір қадамда/кезеңде ең айқын және дереу пайда ұсынатын шешім. Бұл алгоритмді қарастыру үшін біз өте кең таралған мәселені таңдаймыз - рюкзак туралы. Бір секундқа ұры екеніңді көрсетейік. Түнде рюкзакпен дүкенге кіріп кеттің, алдыңда ұрлайтын тауарлардың қатары тұр. Бірақ сонымен бірге рюкзактың сыйымдылығы шектеулі - 30 шартты бірліктен аспайды. Бұл ретте сіз рюкзактарыңызға сыйатын максималды құны бар тауарлар жинағын алып жүргіңіз келеді. Нені қою керектігін қалай шешесіз? Сонымен, сөмке мәселесінің ашкөз алгоритмі келесі қадамдардан тұрады (барлық нысандар сөмкеге сәйкес келеді деп есептейміз):

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 – нысанды жасау кезінде орнатылатын рюкзактың сыйымдылығы;
• заттар — рюкзактағы заттар;
• 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 бірлік сөмке нысанын жасаңыз. Әрі қарай, біз элементтер мен сөмке нысанын 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());

Біз консольге шығуды аламыз: Біраз жақсырақ, солай емес пе? Ашкөз алгоритм түпкілікті шешім де оңтайлы болады деген үмітпен әр қадамда жергілікті оңтайлы таңдау жасайды. Бұл әрқашан ақтала бермейді, бірақ көптеген мәселелер үшін ашкөз алгоритмдер оңтайлы мүмкіндік береді. Бұл алгоритмнің уақыт күрделілігі O(N) болып табылады , бұл өте жақсы, солай емес пе? Міне, осымен мақаланың бірінші бөлімі аяқталды. Егер сізді осы мақаланың жалғасы қызықтырса, онда олармен байланысты графиктер мен алгоритмдер туралы айтылады, оны мына жерден таба аласыз .