สิ่งที่พวกเขาถามในการสัมภาษณ์: การทบทวนอัลกอริทึม ตอนที่ 1

สวัสดีตอนบ่ายทุกคน! อัลกอริธึมประเภทต่างๆ ถูกใช้ในโครงการบ่อยกว่าที่คุณคิด ตัวอย่างเช่น เราจำเป็นต้องจัดเรียงข้อมูลบางอย่างตามพารามิเตอร์ (คอลัมน์) บางตัว เพื่อที่เราจะได้สำรวจข้อมูลเหล่านั้นได้โดยไม่ต้องใช้ความพยายามมากนัก ดังนั้นจึงไม่มีอะไรแปลกที่ในระหว่างการสัมภาษณ์งานพวกเขาอาจถูกถามเกี่ยวกับอัลกอริธึมพื้นฐานอย่างใดอย่างหนึ่งและอาจได้รับมอบหมายให้ใช้งานโดยใช้โค้ด และเนื่องจากคุณอยู่ในไซต์นี้ ฉันจึงกล้าที่จะเดาว่าคุณเขียนด้วยภาษา Java ดังนั้นวันนี้ฉันขอเชิญคุณมาทำความคุ้นเคยกับอัลกอริธึมพื้นฐานและตัวอย่างเฉพาะของการนำไปใช้งานใน Java โดยบางคนฉันหมายถึง:

1. ภาพรวมของอัลกอริธึมการเรียงลำดับอาเรย์:
   • การเรียงลำดับฟอง
   • การเรียงลำดับการเลือก
   • การเรียงลำดับการแทรก
   • การเรียงลำดับเปลือก
   • จัดเรียงอย่างรวดเร็ว
   • ผสานการเรียงลำดับ
2. อัลกอริธึมโลภ
3. อัลกอริธึมการค้นหาเส้นทาง:
   • คลานไปในเชิงลึก
   • เดินกว้าง
4. อัลกอริธึมการขนส่งเป็นอัลกอริธึมของ Dijkstra

เพื่อไม่ให้เป็นการเสียเวลา เรามาลงมือทำธุรกิจกันดีกว่า

1. ภาพรวมของอัลกอริธึมการเรียงลำดับ

การเรียงลำดับฟอง

อัลกอริธึมการเรียงลำดับนี้ขึ้นชื่อเรื่องความเรียบง่ายเป็นหลัก แต่ก็มีความเร็วในการดำเนินการที่ต่ำที่สุดเช่นกัน เป็นตัวอย่าง ให้พิจารณาการเรียงลำดับแบบบับเบิลสำหรับตัวเลขจากน้อยไปหามาก ลองจินตนาการถึงห่วงโซ่ของตัวเลขที่สุ่มไว้ซึ่งจะดำเนินการตามขั้นตอนต่อไปนี้ โดยเริ่มจากจุดเริ่มต้นของห่วงโซ่:

• เปรียบเทียบตัวเลขสองตัว
• หากตัวเลขทางด้านซ้ายมากกว่า ให้สลับพวกมัน
• เลื่อนไปทางขวาหนึ่งตำแหน่ง

หลังจากผ่านห่วงโซ่ทั้งหมดและทำตามขั้นตอนเหล่านี้แล้ว เราจะพบว่าจำนวนที่มากที่สุดอยู่ที่ส่วนท้ายของชุดตัวเลขของเรา จากนั้นให้ดำเนินการผ่านห่วงโซ่เดียวกันทุกประการโดยทำตามขั้นตอนที่อธิบายไว้ข้างต้น แต่คราวนี้เราจะไม่รวมองค์ประกอบสุดท้ายของรายการ เนื่องจากเป็นองค์ประกอบที่ใหญ่ที่สุดและอยู่ในตำแหน่งสุดท้ายแล้วตามที่ควรจะเป็น ขอย้ำอีกครั้งว่าเราจะได้องค์ประกอบสุดท้ายที่อยู่ท้ายชุดตัวเลขที่ต้องการ ดังนั้นตัวเลขที่ใหญ่ที่สุดสองตัวก็จะเข้ามาแทนที่แล้ว และเริ่มต้นเส้นทางตามสายโซ่อีกครั้งโดยไม่รวมองค์ประกอบที่มีอยู่แล้วจนกว่าองค์ประกอบทั้งหมดจะอยู่ในลำดับที่ต้องการ มาดูการใช้งาน Bubble sort ในโค้ด 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 การส่งผ่านเหล่านี้จะถูกทำซ้ำอีกครั้งจนกว่าองค์ประกอบทั้งหมดจะถูกจัดเรียง การใช้งานใน Java:

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² ) . สำหรับผู้ที่ต้องการเรียนรู้เพิ่มเติมเกี่ยวกับอัลกอริทึมนี้ ฉันขอแนะนำเนื้อหานี้

การเรียงลำดับการแทรก

ขอยกตัวอย่างอีกครั้ง ลองใช้ชุดตัวเลขที่เราต้องการจัดเรียงจากน้อยไปหามาก อัลกอริทึมนี้ประกอบด้วยการวางเครื่องหมายทางด้านซ้ายซึ่งองค์ประกอบจะถูกจัดเรียงบางส่วนระหว่างกันอยู่แล้ว ในแต่ละขั้นตอนของอัลกอริธึม องค์ประกอบใดองค์ประกอบหนึ่งจะถูกเลือกและวางในตำแหน่งที่ต้องการในลำดับที่จัดเรียงไว้แล้ว ดังนั้นส่วนที่จัดเรียงจะขยายต่อไปจนกว่าจะดูองค์ประกอบทั้งหมดแล้ว คุณอาจถามว่า: ฉันจะหาส่วนขององค์ประกอบที่จัดเรียงไว้แล้วได้จากที่ไหน และหลังจากนั้นคุณต้องใส่เครื่องหมาย? แต่อาร์เรย์ขององค์ประกอบแรกก็ถูกจัดเรียงแล้วใช่ไหม? มาดูการใช้งานใน Java:

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 } โดย ซึ่งเราใช้อัลกอริธึมการเรียงลำดับการแทรกและรับ : { 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 = 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 )

จัดเรียงอย่างรวดเร็ว

นี่เป็นหนึ่งในอัลกอริธึมที่ได้รับความนิยมมากที่สุดดังนั้นจึงควรให้ความสนใจเป็นพิเศษ สาระสำคัญของอัลกอริธึมนี้คือองค์ประกอบ Pivot จะถูกเลือกจากรายการองค์ประกอบ โดยพื้นฐานแล้วคือองค์ประกอบใดๆ ที่ต้องเรียงลำดับค่าที่เหลือ ค่าที่น้อยกว่าที่อยู่ทางด้านซ้าย ค่าที่มากกว่าที่อยู่ทางขวา ถัดไปส่วนด้านขวาและด้านซ้ายจะถูกเลือกโดยองค์ประกอบสนับสนุนและสิ่งเดียวกันนี้เกิดขึ้น: ค่าจะถูกจัดเรียงโดยสัมพันธ์กับองค์ประกอบเหล่านี้ จากนั้นองค์ประกอบสนับสนุนจะถูกเลือกจากส่วนที่เป็นผลลัพธ์ - และต่อไปเรื่อย ๆ จนกว่าเราจะได้รับการเรียงลำดับ แถว. อัลกอริทึมนี้ใน 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 выхода из рекурсии,  если длина массива равна 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} . สิ่งนี้จะมีลักษณะอย่างไรในโค้ด Java ในการประมวลผลอัลกอริทึมนี้จะสะดวกสำหรับเราที่จะใช้การเรียกซ้ำ:

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. คุณเรียงลำดับรายการทั้งหมดแล้วหรือยัง? ถ้าไม่เรากลับไปที่จุดที่ 1 ถ้าใช่เราออกจากร้านเนื่องจากเป้าหมายของเราที่นี่เสร็จสมบูรณ์แล้ว

ลองดูอันนี้แต่ในจาวา นี่คือลักษณะของคลาส Item:

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คือความจุของเป้สะพายหลังของเรา ซึ่งกำหนดไว้เมื่อสร้างวัตถุ
• รายการ — สิ่งของในกระเป๋าเป้สะพายหลัง;
• 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 หน่วย ต่อไป เราจะส่งองค์ประกอบและอ็อบเจ็กต์ bag ไปยัง เมธอด 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<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)ซึ่งค่อนข้างดีใช่ไหม ด้วยเหตุนี้ส่วนแรกของบทความนี้จึงสิ้นสุดลงแล้ว หากคุณสนใจความต่อเนื่องของบทความนี้ซึ่งจะพูดถึงกราฟและอัลกอริธึมที่เกี่ยวข้อง คุณสามารถค้นหาได้ที่นี่ .