ملازمت کے انٹرویوز سے سوال و جواب: جاوا میں الگورتھم، حصہ 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²) ہے، کیونکہ ہمارے پاس نیسٹڈ لوپس ہیں۔ عناصر پر بیرونی لوپ 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} The صف کچھ زیادہ ترتیب دی گئی ہے، ہے نا؟ اگلا وقفہ 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 ) تک ہیں۔

Quicksort

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

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

بلاشبہ، 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); // 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;
   }
}

جیسا کہ فوری ترتیب میں ہے، ہم تکراری طریقہ کو ایک درمیانی طریقہ میں منتقل کرتے ہیں تاکہ صارف کو ترتیب دینے کے لیے صرف صف فراہم کرنے کی ضرورت ہو اور اسے کوئی اضافی ڈیفالٹ دلائل فراہم کرنے کی فکر نہ ہو۔ اس الگورتھم میں Quicksort کے ساتھ مماثلتیں ہیں، اور حیرت انگیز طور پر اس پر عمل درآمد کی رفتار ایک جیسی ہے: O(N*logN)۔

2. لالچی الگورتھم

لالچی الگورتھم ایک ایسا نقطہ نظر ہے جہاں ہر مرحلے پر مقامی طور پر بہترین فیصلے کیے جاتے ہیں، اس مفروضے کے ساتھ کہ حتمی حل بھی بہترین ہوگا۔ "بہترین" حل وہی ہوگا جو کسی خاص مرحلے/مرحلے پر سب سے زیادہ واضح اور فوری فائدہ پیش کرتا ہو۔ اس الگورتھم کو دریافت کرنے کے لیے، آئیے ایک کافی عام مسئلہ لیتے ہیں — knapsack مسئلہ۔ ایک لمحے کے لیے دکھاوا کریں کہ آپ چور ہیں۔ آپ رات کو ایک نیپ سیک (بیک بیگ) کے ساتھ ایک اسٹور میں گھس گئے ہیں۔ آپ کے سامنے کئی سامان ہیں جو آپ چوری کر سکتے ہیں۔ لیکن ایک ہی وقت میں، آپ کے نیپ سیک کی صلاحیت محدود ہے۔ یہ 30 یونٹ سے زیادہ وزن نہیں لے سکتا۔ آپ سامان کا سب سے قیمتی سیٹ بھی لے جانا چاہتے ہیں جو بیگ میں فٹ ہوگا۔ آپ کیسے طے کرتے ہیں کہ آپ کے بیگ میں کیا ڈالنا ہے؟ لہذا، نیپ سیک کے مسئلے کے لیے لالچی الگورتھم درج ذیل مراحل پر مشتمل ہے (ہم فرض کرتے ہیں کہ تمام اشیاء کو نیپ سیک میں رکھا جا رہا ہے):

1. سب سے مہنگی چیز کا انتخاب کریں جو ابھی تک نہیں لیا گیا ہے۔
2. اگر یہ تھیلی میں فٹ ہو جائے تو اسے اندر رکھ دیں، اگر نہیں، تو چھوڑ دیں۔
3. کیا ہم پہلے ہی سب کچھ چوری کر چکے ہیں؟ اگر نہیں۔

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

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

• میکس ویٹ ہمارے بیگ کی صلاحیت ہے، جو اس وقت سیٹ ہوتی ہے جب ہم کوئی چیز بناتے ہیں۔
• اشیاء ہمارے بیگ میں موجود اشیاء کی نمائندگی کرتی ہیں۔
• 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 یونٹ کی گنجائش کے ساتھ ایک بیگ آبجیکٹ بناتے ہیں۔ اگلا، ہم آئٹمز اور بیگ آبجیکٹ کو فل بیک پیک طریقہ پر منتقل کرتے ہیں، جو ہمارے لالچی الگورتھم کے مطابق نیپ سیک کو بھرتا ہے:

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 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) ہے۔ بہت اچھا، ہہ؟