Các dự án phát triển sử dụng các thuật toán khác nhau thường xuyên hơn bạn nghĩ. Ví dụ: giả sử chúng ta cần sắp xếp một số dữ liệu theo các tham số (cột) nhất định để có thể điều hướng qua dữ liệu mà không cần nỗ lực nhiều. Vì vậy, sẽ không có gì lạ khi một người phỏng vấn xin việc hỏi bạn về một thuật toán cơ bản cụ thể và có thể giao nhiệm vụ thực hiện thuật toán đó bằng cách sử dụng mã. Và vì bạn đang ở trên trang web này, tôi sẽ mạnh dạn cho rằng bạn đang viết bằng Java. Đó là lý do tại sao hôm nay tôi khuyên bạn nên tự làm quen với một số thuật toán cơ bản và các ví dụ cụ thể về cách triển khai chúng trong Java. Bởi "một số", ý tôi là:
Tổng quan về thuật toán sắp xếp mảng:
sắp xếp bong bóng,
sắp xếp lựa chọn,
sắp xếp chèn,
phân loại vỏ,
sắp xếp nhanh chóng,
hợp nhất sắp xếp,
thuật toán tham lam
Thuật toán tìm đường
tìm kiếm theo chiều sâu
tìm kiếm theo chiều rộng
Thuật toán Dijkstra's Shortest Path First
Chà, không có gì khó chịu nữa, hãy bắt tay vào công việc.
1. Tổng quan về thuật toán sắp xếp
sắp xếp bong bóng
Thuật toán sắp xếp này được biết đến chủ yếu vì tính đơn giản của nó, nhưng nó cũng là một trong những thuật toán chậm nhất. Ví dụ: hãy xem xét sắp xếp bong bóng cho các số theo thứ tự tăng dần. Hãy tưởng tượng một dãy số ngẫu nhiên. Chúng tôi sẽ thực hiện các bước sau trên các số này, bắt đầu từ phần đầu của dãy số:
so sánh hai số;
nếu số bên trái lớn hơn thì hoán đổi chúng;
di chuyển một vị trí sang phải.
Sau khi thực hiện các bước này trên toàn bộ dãy số, chúng ta sẽ thấy rằng số lớn nhất nằm ở cuối dãy số của chúng ta. Sau đó, chúng tôi thực hiện một lần vượt qua chuỗi khác, thực hiện chính xác các bước tương tự như trên. Nhưng lần này chúng tôi sẽ không bao gồm phần tử cuối cùng của danh sách, vì nó là số lớn nhất và đã ở chính xác vị trí của nó khi các số được sắp xếp. Một lần nữa, chúng ta sẽ di chuyển số lớn nhất tiếp theo đến cuối dãy của mình. Tất nhiên, điều đó có nghĩa là hai số lớn nhất đang đứng đúng vị trí của chúng. Một lần nữa, chúng tôi thực hiện chuyển qua chuỗi, loại trừ các phần tử đã có sẵn ở vị trí của chúng, cho đến khi tất cả các phần tử theo thứ tự yêu cầu. Chúng ta hãy xem cách sắp xếp bong bóng được triển khai trong mã 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;
}
}
}
}
}
Như bạn có thể thấy, không có gì phức tạp ở đây. Mọi thứ dường như thật tuyệt vời và nó sẽ như vậy nếu không có một thiếu sót - sắp xếp bong bóng diễn ra rất, rất chậm. Đó là độ phức tạp về thời gian là O(N²), vì chúng ta có các vòng lặp lồng nhau. Vòng lặp bên ngoài qua các phần tử được thực hiện N lần. Vòng lặp bên trong cũng được thực hiện N lần. Kết quả là, chúng tôi nhận được các lần lặp N*N hoặc N².
sắp xếp lựa chọn
Thuật toán này tương tự như sắp xếp bong bóng, nhưng nó hoạt động nhanh hơn một chút. Một lần nữa, làm ví dụ, hãy lấy một dãy số mà chúng ta muốn sắp xếp theo thứ tự tăng dần. Bản chất của thuật toán này là lặp tuần tự qua tất cả các số và chọn phần tử nhỏ nhất, chúng ta lấy và hoán đổi với phần tử ngoài cùng bên trái (phần tử thứ 0). Ở đây chúng ta có một tình huống tương tự như sắp xếp bong bóng, nhưng trong trường hợp này, phần tử được sắp xếp của chúng ta sẽ là nhỏ nhất. Do đó, lần duyệt tiếp theo qua các phần tử sẽ bắt đầu từ phần tử có chỉ số 1. Chúng tôi sẽ lặp lại các lần duyệt này cho đến khi tất cả các phần tử đã được sắp xếp. Thực hiện trong 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;
}
}
}
Thuật toán này ưu việt hơn so với sắp xếp bong bóng, bởi vì ở đây số lượng ca làm việc cần thiết được giảm từ O(N²) xuống O(N). Chúng tôi không điều khiển một yếu tố trong toàn bộ danh sách, nhưng số lượng so sánh vẫn là O(N²).
Sắp xếp chèn
Chúng tôi xem xét một dãy số khác mà chúng tôi muốn sắp xếp theo thứ tự tăng dần. Thuật toán này bao gồm việc đặt một điểm đánh dấu, trong đó tất cả các phần tử ở bên trái của điểm đánh dấu đã được sắp xếp một phần giữa chúng. Tại mỗi bước của thuật toán, một trong các phần tử sẽ được chọn và đặt vào vị trí mong muốn trong dãy đã được sắp xếp một phần. Do đó, phần được sắp xếp sẽ phát triển cho đến khi tất cả các phần tử đã được kiểm tra. Bạn đang tự hỏi làm thế nào bạn có được tập hợp con của các phần tử đã được sắp xếp và cách chúng tôi xác định vị trí đặt điểm đánh dấu? Nhưng mảng chứa phần tử đầu tiên đã được sắp xếp rồi phải không? Chúng ta hãy xem việc triển khai trong 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
}
}
}
Loại sắp xếp này vượt trội hơn so với các loại được mô tả ở trên, bởi vì mặc dù thực tế là nó có cùng thời gian chạy O(N²), thuật toán này nhanh gấp đôi so với sắp xếp bong bóng và nhanh hơn một chút so với sắp xếp lựa chọn.
phân loại vỏ
Sắp xếp này về cơ bản là một sắp xếp chèn sửa đổi. Tôi đang nói về cái gì vậy? Hãy đặt những điều đầu tiên lên hàng đầu. Trước tiên chúng ta phải chọn một khoảng thời gian. Có nhiều cách tiếp cận để đưa ra lựa chọn này. Chúng tôi sẽ không đi vào quá nhiều chi tiết về điều này. Hãy chia mảng của chúng ta làm đôi và lấy một số nào đó — đây sẽ là khoảng của chúng ta. Vì vậy, nếu chúng ta có 9 phần tử trong mảng thì khoảng của chúng ta sẽ là 9/2 = 4,5. Chúng tôi loại bỏ phần phân số và nhận được 4, vì chỉ số mảng chỉ có thể là số nguyên. Chúng tôi sẽ sử dụng khoảng thời gian này để thành lập các nhóm của chúng tôi. Nếu một phần tử có chỉ số 0, thì chỉ số của phần tử tiếp theo trong nhóm của nó là 0+4, nghĩa là 4. Phần tử thứ ba sẽ có chỉ số 4+4, phần tử thứ tư - 8+4, v.v. Trong nhóm thứ hai, phần tử đầu tiên sẽ là 1,5,9... Trong nhóm thứ ba và thứ tư, tình hình sẽ giống nhau. Kết quả là, từ mảng số {6,3,8,8,6,9,4,11,1} ta được bốn nhóm: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Họ giữ nguyên vị trí của mình trong mảng chung, nhưng chúng tôi đã đánh dấu là thành viên của cùng một nhóm: {6,3,8,8,6,9,4,11,1} Tiếp theo, chèn sắp xếp được áp dụng cho các nhóm này và sau đó chúng trông như thế này: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Trong mảng tổng quát, các ô do các nhóm chiếm giữ sẽ không thay đổi, nhưng thứ tự bên trong của chúng sẽ thay đổi, theo thứ tự của các nhóm trên: {1,3,4,8,6,9,8,11,6} Mảng đã trở thành một trật tự hơn một chút, phải không? Khoảng tiếp theo sẽ chia cho 2: 4/2 = 2 Ta có hai nhóm: I—{1,4,6,8,6} II—{3,8,9,11} Trong mảng tổng quát, ta có : {1,3,4,8,6,9,8,11,6} Chúng tôi chạy thuật toán sắp xếp chèn trên cả hai nhóm và nhận được mảng này: {1,3,4,8,6,9,6, 11, 8} Bây giờ mảng của chúng ta gần như đã được sắp xếp. Chúng tôi cần thực hiện lần lặp cuối cùng của thuật toán: chúng tôi chia khoảng cho 2: 2/2 = 1. Chúng tôi nhận được một nhóm bao gồm toàn bộ mảng: {1,3,4,8,6,9,6,11 ,8} Chạy thuật toán sắp xếp chèn trên đó, chúng tôi nhận được: {1,3,4,6,6,8,8,9,11} Hãy xem cách chúng tôi có thể đưa sắp xếp này vào cuộc sống trong mã 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
}
}
}
Hiện tại, hiệu suất của Shellsort không dễ để mô tả, vì kết quả khác nhau trong các tình huống khác nhau. Ước tính thực nghiệm nằm trong khoảng từ O(N 3/2 ) đến O(N 7/6 ).
Sắp xếp nhanh chóng
Đây là một trong những thuật toán phổ biến nhất, vì vậy nó đáng được đặc biệt chú ý. Ý chính của thuật toán này là một phần tử trục được chọn trong danh sách các phần tử. Chúng tôi sắp xếp tất cả các phần tử khác liên quan đến phần tử trục. Các giá trị nhỏ hơn phần tử trục nằm ở bên trái. Các giá trị lớn hơn nó ở bên phải. Tiếp theo, các phần tử trục cũng được chọn ở phần bên phải và bên trái, và điều tương tự cũng xảy ra: các giá trị được sắp xếp tương ứng với các phần tử này. Sau đó, các phần tử trục được chọn trong các phần mới được tạo, v.v. cho đến khi chúng tôi nhận được một chuỗi được sắp xếp. Việc triển khai Java sau đây của thuật toán này sử dụng đệ quy:
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);
}
}
Không còn nghi ngờ gì nữa, thuật toán sắp xếp nhanh là phổ biến nhất, vì trong hầu hết các tình huống, nó chạy nhanh hơn các thuật toán khác. Độ phức tạp thời gian của nó là O(N*logN).
Hợp nhất sắp xếp
Loại này cũng phổ biến. Đây là một trong nhiều thuật toán dựa trên nguyên tắc "chia để trị". Các thuật toán như vậy trước tiên chia vấn đề thành các phần có thể quản lý được (sắp xếp nhanh là một ví dụ khác về thuật toán như vậy). Vậy ý chính của thuật toán này là gì?
Chia:
Mảng được chia thành hai phần có cùng kích thước. Mỗi phần trong số hai phần này lại được chia thành hai phần nữa, và cứ tiếp tục như vậy cho đến khi còn lại phần không thể chia nhỏ nhất có thể. Ta có phần nhỏ nhất không chia được khi mỗi mảng có một phần tử, tức là mảng đã được sắp xếp sẵn.
chinh phục:
Đây là nơi chúng tôi bắt đầu quá trình đặt tên cho thuật toán: hợp nhất. Để làm điều này, chúng tôi lấy hai mảng được sắp xếp kết quả và hợp nhất chúng thành một. Trong trường hợp này, phần tử nhỏ nhất trong số các phần tử đầu tiên của hai mảng được ghi vào mảng kết quả. Thao tác này được lặp lại cho đến khi tất cả các phần tử trong hai mảng này được sao chép hết. Nghĩa là, nếu chúng ta có hai mảng tối thiểu {6} và {4}, chúng ta sẽ so sánh các giá trị của chúng và tạo ra kết quả được hợp nhất này: {4,6}. Nếu chúng ta đã sắp xếp các mảng {4,6} và {2,8}, trước tiên chúng ta so sánh các giá trị 4 và 2, sau đó viết 2 vào mảng kết quả. Sau đó, 4 và 8 sẽ được so sánh và chúng tôi sẽ viết 4. Cuối cùng, 6 và 8 sẽ được so sánh. Theo đó, chúng tôi sẽ viết 6 và chỉ sau đó chúng tôi sẽ viết 8. Kết quả là, chúng tôi nhận được mảng hợp nhất sau: {2,4,6,8}. Điều này sẽ trông như thế nào trong mã Java? Để chạy thuật toán này, sẽ thuận tiện cho chúng ta sử dụng đệ quy:
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;
}
}
Như trong sắp xếp nhanh, chúng tôi chuyển phương thức đệ quy sang một phương thức trung gian để người dùng chỉ cần cung cấp mảng cần sắp xếp và không phải lo lắng về việc cung cấp thêm bất kỳ đối số mặc định nào. Thuật toán này có những điểm tương đồng với quicksort, và không có gì ngạc nhiên khi tốc độ thực hiện của nó là như nhau: O(N*logN).
2. Thuật toán tham lam
Thuật toán tham lam là một cách tiếp cận trong đó các quyết định tối ưu cục bộ được đưa ra ở mỗi giai đoạn, với giả định rằng giải pháp cuối cùng cũng sẽ tối ưu. Giải pháp “tối ưu” sẽ là giải pháp mang lại lợi ích tức thì và rõ ràng nhất ở bất kỳ bước/giai đoạn cụ thể nào. Để khám phá thuật toán này, chúng ta hãy giải quyết một vấn đề khá phổ biến - vấn đề về chiếc ba lô. Giả vờ một lúc rằng bạn là một tên trộm. Bạn đã đột nhập vào một cửa hàng vào ban đêm với một chiếc ba lô (ba lô). Trước mặt bạn là một số hàng hóa mà bạn có thể ăn cắp. Nhưng đồng thời, chiếc ba lô của bạn có sức chứa hạn chế. Nó có thể mang không quá 30 đơn vị trọng lượng. Bạn cũng muốn mang đi bộ hàng hóa có giá trị nhất sẽ vừa với ba lô. Làm thế nào để bạn xác định những gì để đưa vào túi của bạn? Vì thế,
Chọn mặt hàng đắt nhất chưa được thực hiện.
Nếu nó vừa với ba lô, hãy đặt nó vào. Nếu không, hãy để nó.
Chúng ta đã đánh cắp mọi thứ chưa? Nếu không, chúng tôi quay lại bước 1. Nếu có, thì chúng tôi nhanh chóng rời khỏi cửa hàng, vì chúng tôi đã hoàn thành những gì chúng tôi phải làm.
Hãy xem xét điều này, nhưng trong Java. Đây là giao diện của lớp 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;
}
}
Không có gì đặc biệt ở đây: ba trường (tên, trọng lượng, giá trị) xác định các đặc điểm của mặt hàng. Ngoài ra, như bạn có thể thấy, giao diện So sánh được triển khai để cho phép chúng tôi sắp xếp các Mặt hàng của mình theo giá. Tiếp theo, chúng ta sẽ xem xét lớp Bag, đại diện cho chiếc ba lô của chúng ta:
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 là sức chứa của ba lô, được đặt khi chúng ta tạo một đối tượng;
các mục đại diện cho các đối tượng trong ba lô của chúng tôi;
currentWeight , currentValue — các trường này lưu trữ trọng lượng và giá trị hiện tại của tất cả các vật phẩm trong ba lô, mà chúng tôi tăng lên khi thêm một vật phẩm mới trong phương thức addItem.
Dù sao đi nữa, bây giờ chúng ta hãy đến lớp nơi diễn ra tất cả các hành động:
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());
}
}
Đầu tiên, chúng tôi tạo một danh sách các mục và sắp xếp nó. Chúng tôi tạo một đối tượng túi có sức chứa 30 đơn vị. Tiếp theo, chúng tôi chuyển các mục và đối tượng túi cho phương thức fillBackpack, phương thức này sẽ lấp đầy chiếc ba lô theo thuật toán tham lam của chúng tôi:
Nó khá đơn giản: chúng tôi bắt đầu xem qua danh sách các mặt hàng được sắp xếp theo chi phí và cho chúng vào túi nếu khả năng của nó cho phép. Nếu không đủ chỗ, thì mục đó sẽ bị bỏ qua và chúng tôi sẽ tiếp tục duyệt qua các mục còn lại cho đến khi đến cuối danh sách. Khi chúng tôi chạy chính, đây là đầu ra của bàn điều khiển, chúng tôi sẽ nhận được:
Trọng lượng của chiếc ba lô là 29. Tổng giá trị của các vật phẩm trong chiếc ba lô là 3700
Đây là một ví dụ về thuật toán tham lam: ở mỗi bước, một giải pháp tối ưu cục bộ được chọn và cuối cùng, bạn sẽ nhận được một giải pháp tối ưu toàn cục. Trong trường hợp của chúng tôi, lựa chọn tốt nhất là mặt hàng đắt nhất. Nhưng đây có phải là giải pháp tốt nhất? Bạn có nghĩ rằng có thể cải thiện giải pháp của chúng tôi một chút để lấp đầy ba lô của chúng tôi bằng những vật phẩm có tổng giá trị thậm chí còn lớn hơn không? Chúng ta hãy xem làm thế nào điều này có thể được thực hiện.
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());
}
}
}
Ở đây, trước tiên chúng tôi tính tỷ lệ giá trị trên trọng lượng cho từng mặt hàng. Điều này cho chúng ta biết giá trị của từng đơn vị của một mặt hàng nhất định. Và sau đó chúng tôi sử dụng các tỷ lệ này để sắp xếp các mặt hàng của mình và thêm chúng vào túi của chúng tôi. Hãy chạy như sau:
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());
Chúng tôi nhận được đầu ra bảng điều khiển này:
Trọng lượng của chiếc ba lô là 29. Tổng chi phí của các mặt hàng trong chiếc ba lô là 4150
Tốt hơn một chút, phải không? Thuật toán tham lam đưa ra lựa chọn tối ưu cục bộ ở mỗi bước, hy vọng rằng giải pháp cuối cùng cũng sẽ tối ưu. Giả định này không phải lúc nào cũng hợp lệ, nhưng đối với nhiều tác vụ, thuật toán tham lam thực sự mang lại giải pháp cuối cùng tối ưu. Độ phức tạp thời gian của thuật toán này là O(N). Khá tốt nhỉ?
Và vì bạn đang ở trên trang web này, tôi sẽ mạnh dạn cho rằng bạn đang viết bằng Java. Đó là lý do tại sao hôm nay tôi khuyên bạn nên tự làm quen với một số thuật toán cơ bản và các ví dụ cụ thể về cách triển khai chúng trong Java. Bởi "một số", ý tôi là:
GO TO FULL VERSION