نوڪريءَ جي انٽرويوز کان سوال ۽ جواب: جاوا ۾ الگورتھم، حصو 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} صف ٿورو وڌيڪ ترتيب ڏني وئي آهي، ڇا اهو ناهي؟ ايندڙ وقفو 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);
   }
}

بغير ڪنهن شڪ ۾، Quicksort algorithm تمام مشهور آهي، ڇاڪاڻ ته اڪثر حالتن ۾ اهو ٻين جي ڀيٽ ۾ تيز هلندو آهي. ان جي وقت جي پيچيدگي O (N*logN) آهي.

ضم ڪرڻ جي ترتيب

هي قسم پڻ مشهور آهي. اهو ڪيترن ئي الگورتھم مان هڪ آهي جيڪو "ورهايو ۽ فتح" جي اصول تي ڀاڙي ٿو. اهڙا الگورتھم پهريون ڀيرو مسئلي کي منظم حصن ۾ ورهائيندا آهن (Quicksort اهڙي الگورتھم جو ٻيو مثال آهي). پوء هن الگورتھم جو خلاصو ڇا آهي؟

ورهايو:

صف کي تقريبن ساڳئي سائيز جي ٻن حصن ۾ ورهايو ويو آهي. انهن ٻن حصن مان هر هڪ کي وڌيڪ ٻن حصن ۾ ورهايو ويندو آهي، ۽ ائين ئي آهي، جيستائين ننڍا ننڍا ممڪن ناقابل تقسيم حصا باقي رهن. اسان وٽ ننڍا ننڍا حصا آهن جيڪي ورهائي نه سگھندا آهن جڏهن هر صف ۾ هڪ عنصر هوندو آهي، يعني هڪ صف جيڪا اڳ ۾ ئي ترتيب ڏنل آهي.

فتح ڪرڻ:

هي اهو آهي جتي اسان اهو عمل شروع ڪريون ٿا جنهن الورورٿم کي ان جو نالو ڏنو: ضم. هن کي ڪرڻ لاء، اسان ٻن نتيجن جي ترتيب ڏنل صفن کي وٺو ۽ انهن کي هڪ ۾ ملائي. انهي صورت ۾، ٻن صفن جي پهرين عناصر جو ننڍڙو ننڍڙو نتيجو صف ۾ لکيو ويو آهي. اهو آپريشن بار بار ڪيو ويندو آهي جيستائين انهن ٻن صفن ۾ سڀني عناصر کي نقل ڪيو ويو آهي. اهو آهي، جيڪڏهن اسان وٽ ٻه گهٽ ۾ گهٽ صفون آهن {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. لالچي الگورتھم

هڪ لالچ الورورٿم هڪ طريقو آهي جتي هر اسٽيج تي مقامي طور تي بهتر فيصلا ڪيا ويندا آهن، انهي فرض سان ته حتمي حل پڻ بهتر هوندو. ”بهترين“ حل اهو هوندو جيڪو ڪنهن خاص مرحلي/اسٽيج تي تمام واضح ۽ فوري فائدو پيش ڪري. هن الورورٿم کي ڳولڻ لاءِ، اچو ته هڪ تمام عام مسئلو وٺون - ڪتن جو مسئلو. هڪ لمحي لاءِ اهو فرض ڪر ته تون چور آهين. توهان رات جو هڪ دڪان ۾ ٽوڙي ڇڏيو آهي هڪ نفيس (بيڪ پيڪ) سان. توهان جي سامهون ڪيترائي سامان آهن جيڪي توهان چوري ڪري سگهو ٿا. پر ساڳئي وقت، توهان جي نفيس کي محدود گنجائش آهي. اهو وزن جي 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();
   }
}

• maxWeight اسان جي backpack جي گنجائش آهي، جيڪو مقرر ڪيو ويندو آهي جڏهن اسان هڪ اعتراض ٺاهيندا آهيون؛
• شيون اسان جي پيٽ ۾ شين جي نمائندگي ڪن ٿا؛
• 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 طريقي سان منتقل ڪريون ٿا، جيڪو اسان جي لالچي الگورتھم جي مطابق knapsack ڀري ٿو:

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) آهي. تمام سٺو، ها؟