آنچه آنها در مصاحبه می پرسند: بررسی الگوریتم ها، بخش 1

ظهر همگی بخیر! انواع مختلفی از الگوریتم ها بیشتر از آنچه فکر می کنید در پروژه ها استفاده می شوند. به عنوان مثال، ما باید برخی از داده ها را بر اساس پارامترهای خاص (ستون ها) مرتب کنیم تا بتوانیم بدون تلاش زیاد در میان آنها حرکت کنیم. بنابراین، هیچ چیز عجیبی در این واقعیت وجود ندارد که در طول مصاحبه های شغلی ممکن است از آنها در مورد یک یا آن الگوریتم اساسی سؤال شود و شاید وظیفه اجرای آن با استفاده از کد داده شود. و از آنجایی که شما در این سایت هستید، من جرأت می کنم حدس بزنم که شما در جاوا می نویسید. بنابراین، امروز از شما دعوت می کنم تا با چند الگوریتم پایه و نمونه های خاص پیاده سازی آنها در جاوا آشنا شوید. منظور من از برخی:

1. مروری بر الگوریتم های مرتب سازی آرایه:
   • مرتب سازی حبابی،
   • مرتب سازی انتخابی،
   • مرتب سازی درج،
   • مرتب سازی پوسته،
   • مرتب سازی سریع،
   • مرتب سازی ادغام
2. الگوریتم حریص.
3. الگوریتم های مسیریابی:
   • خزیدن در عمق
   • خزیدن گسترده
4. الگوریتم انتقال الگوریتم دایکسترا است.

خوب، بدون بحث بیشتر، بیایید به کار خود بپردازیم.

1. مروری بر الگوریتم های مرتب سازی

مرتب سازی حبابی

این الگوریتم مرتب سازی در درجه اول به دلیل سادگی شناخته شده است، اما یکی از پایین ترین سرعت های اجرا را نیز دارد. به عنوان مثال، مرتب سازی حبابی را برای اعداد به ترتیب صعودی در نظر بگیرید. بیایید زنجیره ای از اعداد تصادفی را تصور کنیم که مراحل زیر برای آنها انجام می شود و از ابتدای زنجیره شروع می شود:

• مقایسه دو عدد؛
• اگر عدد سمت چپ بیشتر است، آنها را عوض کنید.
• یک موقعیت را به سمت راست حرکت دهید.

پس از گذراندن کل زنجیره و انجام این مراحل، متوجه می شویم که بیشترین عدد در انتهای سری اعداد ما قرار دارد. در مرحله بعد، دقیقاً همان عبور از امتداد زنجیره انجام می شود و مراحل توضیح داده شده در بالا انجام می شود. اما این بار ما آخرین عنصر لیست را درج نمی کنیم، زیرا بزرگترین است و در حال حاضر در آخرین مکان است، همانطور که باید باشد. باز هم، آخرین عنصر را در پایان سری اعداد مورد نظر خود دریافت خواهیم کرد. بر این اساس، دو عدد بزرگ در حال حاضر در جای خود خواهند بود. و دوباره عبور از امتداد زنجیره شروع می شود، به استثنای عناصری که از قبل در جای خود قرار دارند، تا زمانی که همه عناصر به ترتیب مورد نیاز قرار گیرند. بیایید به پیاده سازی مرتب سازی حبابی در کد جاوا نگاه کنیم:

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 آغاز می شود. دوباره، این عبورها تکرار می شوند تا زمانی که همه عناصر مرتب شوند. پیاده سازی در جاوا:

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² باقی می‌ماند. ) . برای کسانی که مایل به کسب اطلاعات بیشتر در مورد این الگوریتم هستند، این مطالب را توصیه می کنم .

مرتب سازی درج

یک بار دیگر، به عنوان مثال، یک سری از اعداد را که می خواهیم به ترتیب صعودی مرتب کنیم، در نظر می گیریم. این الگوریتم شامل قرار دادن یک نشانگر است که در سمت چپ آن عناصر تا حدی بین خودشان مرتب شده اند. در هر مرحله از الگوریتم، یکی از عناصر انتخاب شده و در موقعیت مورد نظر در توالی از قبل مرتب شده قرار می گیرد. بنابراین قسمت مرتب شده تا زمانی که همه عناصر بررسی شوند به رشد خود ادامه می دهد. ممکن است بپرسید: از کجا می توانم آن قسمت از عناصر را که قبلا مرتب شده اند و پس از آن باید یک نشانگر قرار دهید را تهیه کنم؟ اما آرایه عنصر اول از قبل مرتب شده است، اینطور نیست؟ بیایید به پیاده سازی در جاوا نگاه کنیم:

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 } بیایید ببینیم چگونه می توانیم این مرتب سازی را در کد جاوا نمایش دهیم:

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

در حال حاضر، اثربخشی مرتب سازی پوسته واقعاً اثبات نشده است، زیرا نتایج در موقعیت های مختلف متفاوت است. تخمین های به دست آمده از آزمایش ها از O(N ^3/2 ) تا O(N ^7/6 ) متغیر است .

مرتب سازی سریع

این یکی از محبوب ترین الگوریتم ها است و بنابراین ارزش توجه ویژه را دارد. ماهیت این الگوریتم این است که یک عنصر محوری از لیستی از عناصر انتخاب می شود - اساساً هر عنصری که مقادیر باقی مانده باید بر اساس آن مرتب شوند. مقادیر کمتر از آن در سمت چپ، مقادیر بیشتر از آن در سمت راست هستند. در مرحله بعد، قسمت های راست و چپ نیز توسط عنصر پشتیبان انتخاب می شوند و همین اتفاق می افتد: مقادیر نسبت به این عناصر مرتب می شوند، سپس عناصر پشتیبان از قسمت های به دست آمده انتخاب می شوند - و به همین ترتیب تا زمانی که مرتب سازی کنیم. ردیف این الگوریتم در جاوا با استفاده از 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);
   }
}

بدون شک، الگوریتم مرتب‌سازی سریع محبوب‌ترین الگوریتم در نظر گرفته می‌شود، زیرا در اکثر موقعیت‌ها سریع‌تر از سایرین در زمان 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} . این در کد جاوا چگونه به نظر می رسد؟ برای پردازش این الگوریتم، استفاده از 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;
   }
}

مانند مرتب‌سازی سریع، روش بازگشتی را به یک روش میانی منتقل می‌کنیم تا کاربر نیازی به تنظیم آرگومان‌های پیش‌فرض اضافی نداشته باشد، بلکه فقط می‌تواند آرایه‌ای را که باید مرتب‌سازی شود مشخص کند. از آنجایی که این الگوریتم شبیه به پاک کردن سریعتر است، سرعت اجرای آن یکسان است - O(N*logN) .

2. الگوریتم های حریص

الگوریتم حریص رویکردی است که تصمیمات بهینه محلی را در هر مرحله می گیرد و فرض می کند که راه حل نهایی نیز بهینه خواهد بود. راه حل "بهینه" راه حلی است که آشکارترین و فوری ترین مزیت را در یک مرحله/مرحله خاص ارائه می دهد. برای در نظر گرفتن این الگوریتم، یک مشکل نسبتاً رایج را انتخاب می کنیم - در مورد کوله پشتی. بیایید یک لحظه وانمود کنیم که دزد هستید. شب با یک کوله پشتی وارد مغازه شدی و در مقابلت تعدادی کالا هست که می توانی بدزدی. اما در عین حال، ظرفیت کوله پشتی محدود است - بیش از 30 واحد معمولی نیست. در عین حال، شما می خواهید مجموعه ای از کالاها را با حداکثر ارزش حمل کنید که در کوله پشتی شما جای می گیرد. چگونه تصمیم می گیرید چه چیزی را وارد کنید؟ بنابراین، الگوریتم حریص برای مسئله کوله پشتی شامل مراحل زیر است (فرض می کنیم که همه اشیا در کوله پشتی قرار می گیرند):

1. گران ترین مورد را از بین مواردی که هنوز لمس نشده اند انتخاب کنید.
2. اگر در کوله پشتی شما جا می شود، آن را در آنجا قرار دهید و اگر نه، از آن صرف نظر کنید.
3. آیا همه موارد را مرتب کرده اید؟ اگر نه، به نقطه 1 برمی گردیم، اگر بله، از فروشگاه فرار می کنیم، زیرا هدف ما در اینجا تکمیل شده است.

بیایید به این نگاه کنیم، اما در جاوا. کلاس 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;
   }
}

در اینجا چیز خاصی وجود ندارد: سه قسمت - نام ، وزن ، هزینه - برای مشخص کردن ویژگی های کالا. همچنین، همانطور که می بینید، رابط Comparable در اینجا پیاده سازی شده است تا بتوانیم آیتم های خود را بر اساس قیمت مرتب کنیم. در ادامه به کلاس کوله پشتی خود - کیف نگاه می کنیم :

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

همه چیز بسیار ساده است: ما شروع به مرور لیستی از موارد مرتب شده بر اساس هزینه می کنیم و در صورت ظرفیت آنها را در یک کیسه قرار می دهیم. اگر اجازه ندهد، عنصر حذف می شود و عبور از عناصر باقی مانده تا پایان لیست ادامه می یابد. با اجرای 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());

خروجی را به کنسول دریافت می کنیم: کمی بهتر است، اینطور نیست؟ یک الگوریتم حریصانه در هر مرحله یک انتخاب بهینه محلی انجام می دهد با این انتظار که راه حل نهایی نیز بهینه باشد. این همیشه توجیه پذیر نیست، اما برای بسیاری از مشکلات، الگوریتم های حریص بهینه را ارائه می دهند. پیچیدگی زمانی این الگوریتم O(N) است که بسیار خوب است، درست است؟ خوب، با این کار، قسمت اول این مقاله به پایان رسید. اگر علاقه مند به ادامه این مقاله هستید که در مورد نمودارها و الگوریتم های مرتبط با آنها صحبت خواهد شد، می توانید آن را در اینجا بیابید .