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

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

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

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

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++) { // 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} دعونا نلقي نظرة على كيف يمكننا إحياء هذا النوع في كود 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 = 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 ).

فرز سريع

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

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. إذا كانت الإجابة بنعم، فسنقوم بالفرار السريع من المتجر، حيث أننا أنجزنا ما جئنا من أجله.

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

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

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

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

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