پرسش و پاسخ از مصاحبه های شغلی: الگوریتم ها در جاوا، بخش 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++) { // An ordinary outer loop
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // Put the sorted number in the proper cell
           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 is the dividing marker
           int temp = array[i]; // Make a temporary copy of the marked element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // Until a smaller element is found
               array[j] = array[j - 1]; // We shift the element to the right
               --j;
           }
           array[j] = temp;   // Insert the marked element in its proper place
       }
   }
}

این نوع مرتب‌سازی نسبت به مواردی که در بالا توضیح داده شد برتر است، زیرا علیرغم اینکه زمان اجرای 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} در آرایه کلی، ما داریم : {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 = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // Shrink the interval
       }
   }
}

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

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

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

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 for exiting recursion if the array length is 0
           return;

       if (min> = max) // Terminate the recursion, since there is nothing to divide
           return;


       int middle = min + (max - min) / 2; // Select the middle
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) { // Swap places
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // Make a recursive call on the elements that are less than middle
           recursionFastSort(array, min, j);

       if (max > i) // Make a recursive call on the elements larger than 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); // Array for sorting
       int[] bufferArr = new int[array1.length];// Buffer array
       return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
           return sortArr;
       }

       // Make a recursive call to get two sorted arrays:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Merge the sorted arrays:
       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 {
   private String name;
   private int weight;
   private int value;

   public Item(String name, int weight, int value) {
       this.name = name;
       this.weight = weight;
       this.value = value;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getValue() {
       return value;
   }

   @Override
   public int compareTo(Item o) {
       return this.value > o.value ? -1 : 1;
   }
}

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

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentValue;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentValue = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentValue() {
       return currentValue;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentValue += item.getValue();
   }
}

• maxWeight ظرفیت کوله پشتی ما است که هنگام ایجاد یک شی تعیین می شود.
• آیتم ها نشان دهنده اشیاء در کوله پشتی ما هستند.
• CurrentWeight , CurrentValue — این فیلدها وزن و ارزش فعلی همه اقلام موجود در کوله پشتی را ذخیره می کنند که با افزودن یک آیتم جدید به روش addItem، این مقدار را افزایش می دهیم.

به هر حال، اکنون به کلاسی می رویم که در آن همه اکشن ها انجام می شود:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("Guitar", 7, 800));
       items.add(new Item("Iron", 6, 500));
       items.add(new Item("Tea pot", 3, 300));
       items.add(new Item("Lamp", 4, 500));
       items.add(new Item("Television", 15, 2000));
       items.add(new Item("Vase", 2, 450));
       items.add(new Item("Mixer", 2, 400));
       items.add(new Item("Blender", 3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
               ". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}

ابتدا لیستی از آیتم ها ایجاد می کنیم و مرتب می کنیم. ما یک شی کیسه با ظرفیت 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 items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getValue() / 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("The weight of the knapsack is " + secondBag.getCurrentWeight() +
       ". The total cost of items in the knapsack is " + secondBag.getCurrentValue());

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