คำถามและคำตอบจากการสัมภาษณ์งาน: อัลกอริทึมใน Java ตอนที่ 1

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

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

เรามาเริ่มธุรกิจกันเลยดีกว่า

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

เรียงฟอง

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

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

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

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

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

นี่เป็นหนึ่งในอัลกอริธึมที่ได้รับความนิยมมากที่สุด ดังนั้นจึงควรให้ความสนใจเป็นพิเศษ สาระสำคัญของอัลกอริทึมนี้คือมีการเลือกองค์ประกอบเดือยในรายการองค์ประกอบ เราจัดเรียงองค์ประกอบอื่น ๆ ทั้งหมดที่สัมพันธ์กับองค์ประกอบเดือย ค่าที่น้อยกว่าองค์ประกอบเดือยจะอยู่ทางด้านซ้าย ค่าที่มากกว่าทางด้านขวา ถัดไป องค์ประกอบ 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 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 นั้นได้รับความนิยมมากที่สุด เนื่องจากในสถานการณ์ส่วนใหญ่ อัลกอริทึม Quicksort จะทำงานเร็วกว่าวิธีอื่น ความซับซ้อนของเวลาคือ 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} สิ่งนี้จะมีลักษณะอย่างไรในโค้ด 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); // 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 ถ้าใช่ เราก็ออกจากร้านอย่างรวดเร็ว เนื่องจากเราได้ทำสิ่งที่เราต้องทำสำเร็จแล้ว

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

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คือความจุของเป้ ซึ่งถูกกำหนดเมื่อเราสร้างวัตถุ
• รายการเป็นตัวแทนของวัตถุในกระเป๋าเป้สะพายหลังของเรา
• 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);
       }
   }
}

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

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) ค่อนข้างดีใช่มั้ย