โครงการพัฒนาใช้อัลกอริทึมต่างๆ บ่อยกว่าที่คุณคิด ตัวอย่างเช่น สมมติว่าเราจำเป็นต้องจัดเรียงข้อมูลบางอย่างตามพารามิเตอร์บางตัว (คอลัมน์) เพื่อให้เรานำทางผ่านข้อมูลได้โดยไม่ต้องใช้ความพยายามมากนัก ดังนั้นจึงไม่แปลกเลยที่ผู้สัมภาษณ์งานจะถามคุณเกี่ยวกับอัลกอริทึมพื้นฐานที่เฉพาะเจาะจง และอาจมอบหน้าที่ในการนำไปใช้งานโดยใช้โค้ด ![คำถามและคำตอบจากการสัมภาษณ์งาน: อัลกอริทึมใน Java ตอนที่ 1 - 1]()
และเนื่องจากคุณอยู่ในเว็บไซต์นี้ ฉันจะกล้าคิดว่าคุณกำลังเขียนด้วยภาษาจาวา นั่นเป็นเหตุผลที่วันนี้ฉันขอแนะนำให้คุณทำความคุ้นเคยกับอัลกอริทึมพื้นฐานและตัวอย่างเฉพาะของวิธีการนำไปใช้ใน Java โดย "บางคน" ฉันหมายถึง:
และเนื่องจากคุณอยู่ในเว็บไซต์นี้ ฉันจะกล้าคิดว่าคุณกำลังเขียนด้วยภาษาจาวา นั่นเป็นเหตุผลที่วันนี้ฉันขอแนะนำให้คุณทำความคุ้นเคยกับอัลกอริทึมพื้นฐานและตัวอย่างเฉพาะของวิธีการนำไปใช้ใน Java โดย "บางคน" ฉันหมายถึง:
- ภาพรวมของอัลกอริธึมการเรียงลำดับอาร์เรย์:
- เรียงฟอง,
- เรียงลำดับการเลือก,
- การเรียงลำดับการแทรก,
- เรียงเปลือก,
- Quicksort,
- เรียงลำดับการผสาน,
- อัลกอริทึมโลภ
- อัลกอริทึมการค้นหาเส้นทาง
- การค้นหาเชิงลึกก่อน
- การค้นหาแบบกว้างก่อน
- อัลกอริทึมเส้นทางที่สั้นที่สุดของ 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;
}
}
}
}
}
เรียงลำดับการเลือก
อัลกอริทึมนี้คล้ายกับการเรียงลำดับแบบฟอง แต่ทำงานเร็วกว่าเล็กน้อย ยกตัวอย่างอีกครั้ง ลองเรียงลำดับตัวเลขที่เราต้องการจัดเรียงจากน้อยไปมาก สาระสำคัญของอัลกอริทึมนี้คือการวนซ้ำตามลำดับของตัวเลขทั้งหมดและเลือกองค์ประกอบที่เล็กที่สุด ซึ่งเราใช้และสลับกับองค์ประกอบด้านซ้ายสุด (องค์ประกอบที่ 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;
}
}
}
การเรียงลำดับการแทรก
เราพิจารณาลำดับตัวเลขอื่นที่เราต้องการจัดเรียงจากน้อยไปหามาก อัลกอริทึมนี้ประกอบด้วยการวางเครื่องหมาย โดยที่องค์ประกอบทั้งหมดทางด้านซ้ายของเครื่องหมายถูกจัดเรียงบางส่วนแล้ว ในแต่ละขั้นตอนของอัลกอริทึม องค์ประกอบหนึ่งจะถูกเลือกและวางในตำแหน่งที่ต้องการในลำดับที่จัดเรียงบางส่วน ดังนั้นส่วนที่เรียงจะโตขึ้นจนกว่าจะตรวจสอบองค์ประกอบทั้งหมด คุณสงสัยหรือไม่ว่าคุณได้รับชุดย่อยขององค์ประกอบที่จัดเรียงแล้วอย่างไร และเราจะกำหนดตำแหน่งที่จะวางเครื่องหมายได้อย่างไร แต่อาร์เรย์ที่ประกอบด้วยองค์ประกอบแรกนั้นถูกจัดเรียงแล้วใช่ไหม มาดูการใช้งานใน 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
}
}
}
เรียงเปลือก
การจัดเรียงนี้เป็นการเรียงลำดับการแทรกที่ปรับเปลี่ยนโดยพื้นฐานแล้ว ฉันกำลังพูดถึงอะไร ขอใส่สิ่งแรกก่อน ก่อนอื่นเราต้องเลือกช่วงเวลา มีหลายวิธีในการเลือกนี้ เราจะไม่ลงรายละเอียดมากเกินไปเกี่ยวกับเรื่องนี้ ลองแบ่งอาร์เรย์ของเราออกเป็นสองส่วนแล้วหาจำนวนมา — นี่จะเป็นช่วงเวลาของเรา ดังนั้น ถ้าเรามี 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
}
}
}
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 เป็นอีกตัวอย่างหนึ่งของอัลกอริทึมดังกล่าว) แล้วสาระสำคัญของอัลกอริทึมนี้คืออะไร?แบ่ง:
อาร์เรย์แบ่งออกเป็นสองส่วนที่มีขนาดเท่ากันโดยประมาณ แต่ละส่วนจากสองส่วนนี้จะถูกแบ่งออกเป็นสองส่วน และต่อไปเรื่อยๆ จนกว่าจะเหลือส่วนที่เล็กที่สุดที่แบ่งแยกไม่ได้ เรามีส่วนที่เล็กที่สุดที่แบ่งแยกไม่ได้เมื่อแต่ละอาร์เรย์มีองค์ประกอบเดียว นั่นคือ อาร์เรย์ที่เรียงลำดับแล้วพิชิต:
นี่คือจุดที่เราเริ่มกระบวนการที่ให้ชื่ออัลกอริทึม: ผสาน ในการทำเช่นนี้ เราจะนำอาร์เรย์ที่เรียงลำดับแล้วสองรายการมารวมกันเป็นหนึ่งเดียว ในกรณีนี้ องค์ประกอบแรกที่เล็กที่สุดของสองอาร์เรย์จะถูกเขียนลงในอาร์เรย์ผลลัพธ์ การดำเนินการนี้จะทำซ้ำจนกว่าองค์ประกอบทั้งหมดในอาร์เรย์ทั้งสองนี้จะถูกคัดลอกไป นั่นคือ ถ้าเรามีอาร์เรย์ขั้นต่ำสองตัว {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;
}
}
2. อัลกอริทึมโลภ
อัลกอริทึมแบบตะกละเป็นวิธีการที่มีการตัดสินใจที่เหมาะสมที่สุดในพื้นที่ในแต่ละขั้นตอน โดยมีข้อสันนิษฐานว่าวิธีแก้ปัญหาสุดท้ายก็จะเหมาะสมที่สุดเช่นกัน โซลูชันที่ "เหมาะสมที่สุด" จะเป็นโซลูชันที่ให้ประโยชน์ที่ชัดเจนที่สุดและทันทีในขั้นตอน/ขั้นตอนใดขั้นตอนหนึ่งโดยเฉพาะ ในการสำรวจอัลกอริทึมนี้ เรามาพิจารณาปัญหาที่พบได้บ่อย นั่นคือปัญหาเป้ แสร้งทำเป็นสักครู่ว่าคุณเป็นขโมย คุณได้บุกเข้าไปในร้านตอนกลางคืนพร้อมกับกระเป๋าเป้ (เป้) ข้างหน้าคุณคือสินค้าหลายอย่างที่คุณสามารถขโมยได้ แต่ในขณะเดียวกันเป้ของคุณก็มีความจุจำกัด รับน้ำหนักได้ไม่เกิน 30 หน่วย คุณยังต้องการนำชุดสินค้าที่มีค่าที่สุดที่จะใส่ในกระเป๋าเป้ไปด้วย คุณจะกำหนดสิ่งที่ใส่ลงในกระเป๋าของคุณได้อย่างไร? ดังนั้น,- เลือกของที่แพงที่สุดที่ยังไม่ได้เอาไป
- ถ้าพอดีในเป้ ก็ใส่เข้าไป ถ้าไม่พอดีก็ปล่อยไป
- เราขโมยทุกอย่างไปแล้วหรือ? ถ้าไม่ใช่ เราจะกลับไปที่ขั้นตอนที่ 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คือความจุของเป้ ซึ่งถูกกำหนดเมื่อเราสร้างวัตถุ
- รายการเป็นตัวแทนของวัตถุในกระเป๋าเป้สะพายหลังของเรา
- 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());
}
}
public static void fillBackpack(Bag bag, List<Item> items) {
for (Item item : items) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
bag.addItem(item);
}
}
}
น้ำหนักของเป้คือ 29 มูลค่ารวมของสิ่งของในเป้คือ 3700
นี่คือตัวอย่างของอัลกอริทึมโลภ: ในแต่ละขั้นตอน โซลูชันที่เหมาะสมที่สุดในพื้นที่จะถูกเลือก และท้ายที่สุด คุณจะได้โซลูชันที่เหมาะสมที่สุดทั่วโลก ในกรณีของเรา ตัวเลือกที่ดีที่สุดคือสินค้าที่แพงที่สุด แต่นี่เป็นทางออกที่ดีที่สุดหรือไม่? คุณไม่คิดว่ามันเป็นไปได้ที่จะปรับปรุงวิธีแก้ปัญหาของเราเล็กน้อยเพื่อให้กระเป๋าเป้สะพายหลังของเราเต็มไปด้วยสิ่งของที่มีมูลค่ารวมมากกว่า? ลองมาดูกันว่าวิธีนี้สามารถทำได้อย่างไร
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());
น้ำหนักของเป้คือ 29 ราคารวมของสิ่งของในเป้คือ 4150
ดีขึ้นนิดหน่อยไม่ใช่เหรอ? อัลกอริทึมโลภสร้างทางเลือกที่เหมาะสมที่สุดในทุกขั้นตอน โดยหวังว่าทางออกสุดท้ายจะเหมาะสมที่สุดเช่นกัน สมมติฐานนี้ไม่ถูกต้องเสมอไป แต่สำหรับงานหลายๆ อย่าง อัลกอริทึมแบบละโมบจะให้คำตอบสุดท้ายที่เหมาะสมที่สุด ความซับซ้อนของเวลาของอัลกอริทึมนี้คือ O(N) ค่อนข้างดีใช่มั้ย
GO TO FULL VERSION