وہ انٹرویو میں کیا پوچھتے ہیں: الگورتھم کا جائزہ، حصہ 1

سب کو دوپہر بخیر! مختلف قسم کے الگورتھم پروجیکٹس میں آپ کے خیال سے زیادہ کثرت سے استعمال ہوتے ہیں۔ مثال کے طور پر، ہمیں کچھ ڈیٹا کو مخصوص پیرامیٹرز (کالموں) کے مطابق ترتیب دینے کی ضرورت ہے تاکہ ہم بغیر کسی کوشش کے اس پر جا سکیں۔ اس لیے اس حقیقت میں کوئی عجیب بات نہیں ہے کہ ملازمت کے انٹرویو کے دوران ان سے ایک یا دوسرے بنیادی الگورتھم کے بارے میں پوچھا جا سکتا ہے، اور شاید کوڈ کا استعمال کرتے ہوئے اسے لاگو کرنے کا ٹاسک دیا جا سکتا ہے۔ اور چونکہ آپ اس سائٹ پر ہیں، میں یہ اندازہ لگانے کی کوشش کروں گا کہ آپ جاوا میں لکھتے ہیں۔ لہذا، آج میں آپ کو کچھ بنیادی الگورتھم اور جاوا میں ان کے نفاذ کی مخصوص مثالوں سے واقف ہونے کی دعوت دیتا ہوں۔ کچھ لوگوں سے میرا مطلب ہے:

1. صف ترتیب دینے والے الگورتھم کا جائزہ:
   • بلبلے کی ترتیب،
   • انتخاب کی ترتیب،
   • داخل کرنے کی ترتیب،
   • شیل کی ترتیب،
   • فوری ترتیب،
   • ضم ترتیب.
2. لالچی الگورتھم۔
3. پاتھ فائنڈنگ الگورتھم:
   • گہرائی میں رینگنا
   • وسیع رینگنا.
4. نقل و حمل کا الگورتھم Dijkstra کا الگورتھم ہے۔

ٹھیک ہے، مزید اڈو کے بغیر، آئیے کاروبار پر اترتے ہیں۔

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²) کی وقتی پیچیدگی کے ساتھ بہت، بہت سست ہے ، کیونکہ ہم نے گھونسلا بنایا ہے۔ loops عناصر کے ذریعے خارجی گزرنے کا عمل 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 } By جسے ہم داخل کرنے کے الگورتھم سے گزرتے ہیں اور حاصل کرتے ہیں: { 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 ) تک ہیں ۔

فوری ترتیب

یہ سب سے زیادہ مقبول الگورتھم میں سے ایک ہے، اور اس وجہ سے یہ خصوصی توجہ دینے کے قابل ہے. اس الگورتھم کا نچوڑ یہ ہے کہ ایک محور عنصر کو عناصر کی فہرست سے منتخب کیا جاتا ہے — بنیادی طور پر کوئی بھی عنصر جس کے خلاف باقی اقدار کو ترتیب دینے کی ضرورت ہے۔ اس سے کم قدریں بائیں طرف ہیں، قدریں اس سے زیادہ دائیں طرف ہیں۔ اس کے بعد، دائیں اور بائیں حصوں کو بھی معاون عنصر کے ذریعہ منتخب کیا جاتا ہے اور وہی ہوتا ہے: اقدار کو ان عناصر کے مطابق ترتیب دیا جاتا ہے، پھر معاون عناصر کو نتیجے میں آنے والے حصوں سے منتخب کیا جاتا ہے - اور اسی طرح جب تک کہ ہم ایک ترتیب حاصل نہیں کر لیتے قطار جاوا میں یہ الگورتھم تکرار کا استعمال کرتے ہوئے لاگو کیا جاتا ہے:

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

بلا شبہ، Quicksort الگورتھم کو سب سے زیادہ مقبول سمجھا جاتا ہے، کیونکہ زیادہ تر حالات میں یہ 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. کیا آپ نے تمام اشیاء کو ترتیب دیا ہے؟ اگر نہیں۔

آئیے اس کو دیکھتے ہیں، لیکن جاوا میں۔ آئٹم کی کلاس اس طرح نظر آئے گی:

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

سب کچھ انتہائی آسان ہے: ہم قیمت کے لحاظ سے ترتیب دی گئی اشیاء کی فہرست میں جانا شروع کرتے ہیں اور اگر صلاحیت اجازت دے تو انہیں ایک بیگ میں ڈال دیتے ہیں۔ اگر یہ اجازت نہیں دیتا ہے تو، عنصر کو چھوڑ دیا جائے گا اور باقی عناصر سے گزرنا فہرست کے اختتام تک جاری رہے گا۔ مین کو چلانے سے، ہمیں کنسول میں درج ذیل آؤٹ پٹ ملتا ہے۔ دراصل، یہ لالچی الگورتھم کی ایک مثال ہے: ہر قدم پر مقامی طور پر ایک بہترین حل منتخب کیا جاتا ہے، اور آخر میں آپ کو عالمی سطح پر ایک بہترین حل ملتا ہے۔ ہمارے معاملے میں، بہترین آپشن سب سے مہنگی چیز ہے۔ لیکن کیا یہ بہترین حل ہے؟ کیا آپ کو نہیں لگتا کہ ہم اپنے حل کو تھوڑا سا جدید بنا سکتے ہیں تاکہ ہم ایک بیگ کو زیادہ کل لاگت سے لیس کر سکیں؟ آئیے ایک نظر ڈالتے ہیں کہ یہ کیسے کیا جا سکتا ہے:

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) ہے ، جو کہ بہت اچھی ہے، ٹھیک ہے؟ خیر اس کے ساتھ ہی اس مضمون کا پہلا حصہ اختتام کو پہنچا۔ اگر آپ اس مضمون کے تسلسل میں دلچسپی رکھتے ہیں، جو ان سے متعلق گراف اور الگورتھم کے بارے میں بات کرے گا، تو آپ اسے یہاں حاصل کر سکتے ہیں ۔