ڇا اهي هڪ انٽرويو ۾ پڇن ٿا: الگورتھم جو جائزو، حصو 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²) جي وقت جي پيچيدگي سان ، جڏهن ته اسان nested آهيون. لوپس عناصرن مان خارجي پاسو 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 algorithm سڀ کان وڌيڪ مشهور سمجهيو ويندو آهي، ڇاڪاڻ ته اڪثر حالتن ۾ اهو ٻين کان وڌيڪ تيز هلندو آهي، 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. لالچي الگورتھم

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

• maxWeight اسان جي backpack جي گنجائش آهي، جنهن کي مقرر ڪيو ويو آهي جڏهن اعتراض ٺاهي؛
• شيون - پس منظر ۾ شيون؛
• 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) آهي ، جيڪا تمام سٺي آهي، صحيح؟ خير، ان سان، هن مضمون جو پهريون حصو پڄاڻي تي آيو آهي. جيڪڏهن توهان هن مضمون جي تسلسل ۾ دلچسپي رکو ٿا، جيڪو انهن سان لاڳاپيل گراف ۽ الگورتھم بابت ڳالهائيندو، توهان ان کي ڳولي سگهو ٿا هتي .