ما الذي يسألونه في المقابلة: مراجعة الخوارزميات، الجزء الأول

مساء الخير جميعا! يتم استخدام أنواع مختلفة من الخوارزميات في المشاريع أكثر مما تعتقد. على سبيل المثال، نحتاج إلى فرز بعض البيانات وفقًا لمعلمات معينة (أعمدة) حتى نتمكن من التنقل خلالها دون بذل الكثير من الجهد. لذلك، ليس هناك شيء غريب في حقيقة أنه خلال مقابلات العمل قد يتم سؤالهم عن خوارزمية أساسية أو أخرى، وربما يتم تكليفهم بمهمة تنفيذها باستخدام التعليمات البرمجية. وبما أنك في هذا الموقع، فإنني أجرؤ على تخمين أنك تكتب بلغة جافا. لذلك، أدعوك اليوم للتعرف على بعض الخوارزميات الأساسية والأمثلة المحددة لتطبيقها في Java. وأقصد بالبعض:

1. نظرة عامة على خوارزميات فرز المصفوفة:
   • فقاعة الفرز،
   • اختيار نوع،
   • ترتيب بالإدراج،
   • نوع شل,
   • فرز سريع,
   • دمج النوع.
2. خوارزمية الجشع.
3. خوارزميات تحديد المسار:
   • الزحف في العمق
   • زحف واسع.
4. خوارزمية النقل هي خوارزمية ديكسترا.

حسنًا، دون مزيد من اللغط، فلنبدأ العمل.

1. نظرة عامة على خوارزميات الفرز

فقاعة الفرز

تُعرف خوارزمية الفرز هذه في المقام الأول ببساطتها، ولكنها تتميز أيضًا بواحدة من أقل سرعات التنفيذ. على سبيل المثال، فكر في الفرز الفقاعي للأرقام بترتيب تصاعدي. لنتخيل سلسلة من الأرقام الموضوعة عشوائيًا والتي سيتم تنفيذ الخطوات التالية لها بدءًا من بداية السلسلة:

• قارن بين رقمين؛
• إذا كان الرقم الذي على اليسار أكبر، فقم بتبديلهم؛
• تحريك موضع واحد إلى اليمين.

بعد المرور بالسلسلة بأكملها وتنفيذ هذه الخطوات، سنجد أن العدد الأكبر موجود في نهاية سلسلة الأرقام لدينا. بعد ذلك، يتم تنفيذ نفس المرور على طول السلسلة، باتباع الخطوات الموضحة أعلاه. لكن هذه المرة لن ندرج العنصر الأخير في القائمة، لأنه الأكبر وهو بالفعل في المركز الأخير، كما ينبغي أن يكون. مرة أخرى، سنحصل على العنصر الأخير في نهاية سلسلة الأعداد المعنية. وبناء على ذلك، فإن أكبر رقمين سيكونان في أماكنهما بالفعل. ومرة أخرى يبدأ المرور على طول السلسلة، باستثناء العناصر الموجودة بالفعل، حتى تصبح جميع العناصر بالترتيب المطلوب. دعونا نلقي نظرة على تنفيذ نوع الفقاعة في كود Java:

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} ب المصفوفة العامة: { 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:

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 ) .

فرز سريع

هذه هي واحدة من الخوارزميات الأكثر شعبية، وبالتالي فهي تستحق الاهتمام بشكل خاص. جوهر هذه الخوارزمية هو تحديد عنصر محوري من قائمة العناصر - أي عنصر يجب فرز القيم المتبقية عليه. القيم الأقل منها على اليسار، والقيم الأكبر منها على اليمين. بعد ذلك، يتم تحديد الأجزاء اليمنى واليسرى أيضًا بواسطة العنصر الداعم ويحدث نفس الشيء: يتم فرز القيم بالنسبة لهذه العناصر، ثم يتم اختيار العناصر الداعمة من الأجزاء الناتجة - وهكذا حتى نحصل على فرز صف. يتم تنفيذ هذه الخوارزمية في 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} . كيف سيبدو هذا في كود جافا؟ لمعالجة هذه الخوارزمية، سيكون من المناسب لنا استخدام التكرار:

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، إذا كانت الإجابة بنعم، فإننا نهرب من المتجر، لأن هدفنا هنا قد اكتمل.

دعونا ننظر إلى هذا، ولكن في جافا. هذا هو الشكل الذي ستبدو عليه فئة العنصر:

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

• الوزن الأقصى هو سعة حقيبة الظهر الخاصة بنا، والتي يتم ضبطها عند إنشاء الكائن؛
• العناصر - الأشياء الموجودة في حقيبة الظهر؛
• 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) وهو أمر جيد جدًا، أليس كذلك؟ حسنًا، بهذا يكون الجزء الأول من هذه المقالة قد انتهى. إذا كنت مهتمًا بمواصلة هذه المقالة التي ستتحدث عن الرسوم البيانية والخوارزميات المتعلقة بها، يمكنك العثور عليها هنا .