Что спрашивают на собеседовании: обзор алгоритмов, часть 1

Всем доброго дня суток! Различные виды алгоритмов используются в проектах чаще, чем это может показаться. К примеру, нужно отсортировать некоторые данные по тем or иным параметрам (колонкам), чтобы мы могли без особых усorй перемещаться по ним. Поэтому нет ничего странного в том, что и на собеседованиях при приеме на работу могут спросить о том or ином базовом алгоритме, и возможно, дать задание реализовать его при помощи codeа. А так How вы на этом сайте, я осмелюсь предположить, что вы пишете на Java. Поэтому сегодня я предлагаю вам ознакомиться с некоторыми базовыми алгоритмами и с конкретными примерами их реализации на Java. Под некоторыми я подразумеваю:

1. Обзор алгоритмов сортировки массива:
   • пузырьковая sorting,
   • sorting выбором,
   • sorting вставкой,
   • sorting Шелла,
   • быстрая sorting,
   • sorting слиянием.
2. Жадный алгоритм.
3. Алгоритмы поиска пути:
   • обход в глубину,
   • обход в ширину.
4. Транспортный алгоритм — алгоритм Дейкстры.

What же, без лишних предисловий приступим к делу.

1. Обзор алгоритмов сортировки

Пузырьковая sorting

Данный алгоритм сортировки известен в первую очередь за счёт своей простоты, однако при этом он имеет одну из наиболее низких скоростей выполнения. В качестве примера рассмотрим пузырьковую сортировку для чисел в возрастающем порядке. Представим себе цепочку случайно расставленных чисел, для которых будут выполняться следующие шаги, начиная с начала цепочки:

• сравнить два числа;
• если число слева больше, то поменять их местами;
• перейти на одну позицию вправо.

После прохождения по всей цепочке с выполнением данных шагов мы обнаружим, что наибольшее число оказалось в конце нашего ряда чисел. Далее выполняется точно такой же проход по цепочке с выполнением вышеописанных шагов. Но в этот раз мы не будем включать последний элемент списка, так How он самый большой и уже стоит на последнем месте, How и должен. Опять, же мы получим последний элемент в конце нашего ряда рассматриваемых чисел. Соответственно, уже два наибольших числа будут стоять на своих местах. И опять запускается проход по цепочке за исключением элементов, которые уже на своих местах, до тех пор, пока все элементы не будут стоять в необходимом порядке. Давайте рассмотрим реализацию пузырьковой сортировки в Java-codeе:

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;
             }
         }
       }
   }
}

Как видите, ничего сложного тут нет, и всё вроде бы How здорово, если бы не одно “но”… Пузырьковая sorting весьма и весьма медленная, с временной сложностью O(N²), так How мы имеем вложенные циклы. Внешний проход по elementм выполняется за N раз, внутренний — тоже N раз, и в итоге мы получаем N*N, N² итераций Более подробно изучить данный вид сортировки можно в этой статье.

Сортировка методом выбора

Thuật toán này tương tự như thuật toán sắp xếp theo 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 là tuần tự đi qua tất cả các số và chọn phần tử nhỏ nhất, chúng ta lấy phần tử này và hoán đổi vị trí với phần tử ngoài cùng bên trái (phần tử 0). Ở đây chúng ta gặp tình huống tương tự như sắp xếp nổi bọt, nhưng trong trường hợp này phần tử được sắp xếp sẽ là phần tử nhỏ nhất. Do đó, lần chuyển tiếp theo qua các phần tử sẽ bắt đầu với phần tử ở chỉ mục 1. Một lần nữa, các lần chuyển này sẽ được lặp lại cho đến khi tất cả các phần tử được sắp xếp. Triển khai bằng 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;
       }
   }
}

Thuật toán này vượt trội hơn so với sắp xếp nổi bọt, vì ở đây số lượng hoán vị cần thiết giảm từ O(N²) xuống O(N): chúng tôi không đẩy một phần tử trong toàn bộ danh sách, tuy nhiên, số lượng so sánh vẫn là O(N² ) . Đối với những người muốn tìm hiểu thêm về thuật toán này, tôi khuyên bạn nên sử dụng tài liệu này .

Sắp xếp chèn

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. Thuật toán này bao gồm việc đặt một điểm đánh dấu, ở bên trái của các phần tử sẽ được sắp xếp một phần với nhau. Ở 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ị trí mong muốn trong chuỗi đã được sắp xếp. Vì vậy phần được sắp xếp sẽ tiếp tục phát triển cho đến khi tất cả các phần tử đã được xem xét. Bạn có thể hỏi: tôi có thể lấy phần tử đã được sắp xếp ở đâu và sau đó bạn cần đặt điểm đánh dấu? Nhưng mảng phần tử đầu tiên đã được sắp xếp rồi phải không? Hãy xem cách 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 - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Kiểu sắp xếp này vượt trội hơn so với kiểu được mô tả ở trên, vì mặc dù thực tế là thời gian chạy là như nhau - O(N²) , thuật toán này hoạt động 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. Đọc thêm tại đây .

Phân loại vỏ

Về bản chất, loại sắp xếp này là một loại sắp xếp chèn được sửa đổi. Tôi đang nói về cái gì vậy? Hãy đi theo thứ tự. Một bước được chọn và có nhiều cách tiếp cận cho sự lựa chọn này. Chúng ta sẽ không đi sâu vào vấn đề này quá chi tiết. Hãy chia mảng của chúng ta làm đôi và lấy một số nhất định - đây sẽ là bước của chúng ta. Vì vậy, nếu chúng ta có 9 phần tử trong mảng thì bước 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ỉ là số nguyên. Với bước này, chúng ta sẽ tạo kết nối cho các nhóm của mình. Nếu một phần tử có chỉ mục 0 thì chỉ mục của phần tử tiếp theo trong nhóm của nó là 0+4 , tức là 4 . Phần tử thứ ba sẽ có chỉ mục là 4+4 , phần tử thứ tư sẽ có chỉ mục là 8+4 , v.v. Đối với nhóm thứ hai, phần tử đầu tiên sẽ là 1,5,9…. Ở nhóm thứ ba và thứ tư, mọi thứ sẽ hoàn toàn giống nhau. Kết quả từ dãy số {6,3,8,8,6,9,4,11,1} ta được 4 nhóm: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Chúng giữ nguyên vị trí của mình trong mảng chung, nhưng đối với chúng ta chúng được đá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 } Hơn nữa, trong các nhóm này, quá trình sắp xếp chèn , sau đó các nhóm sẽ trông như sau: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Trong mảng chung, các ô mà các nhóm chiếm giữ sẽ giữ nguyên nhưng thứ tự trong 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 có trật tự hơn một chút phải không? Bước 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} B mảng tổng quát: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Chúng ta duyệt qua cả hai nhóm bằng thuật toán sắp xếp chèn và nhận được một mảng: { 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. Lần lặp cuối cùng của thuật toán vẫn còn: chúng ta chia bước cho 2: 2/2 = 1. Chúng ta có một nhóm, toàn bộ mảng: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } By mà chúng ta thực hiện qua thuật toán sắp xếp chèn và nhận được: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Hãy xem cách chúng ta có thể hiển thị cách sắp xếp này 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 = 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; // уменьшаем наш шаг
       }
   }
}

Hiện tại, hiệu quả của việc phân loại Shell chưa thực sự được chứng minh vì kết quả sẽ khác nhau trong các tình huống khác nhau. Ước tính thu được từ các thí 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à do đó nó đáng được đặc biệt chú ý. Bản chất của thuật toán này là một phần tử trục được chọn từ danh sách các phần tử—về cơ bản là bất kỳ phần tử nào mà các giá trị còn lại cần được sắp xếp theo đó. Các giá trị nhỏ hơn ở bên trái, các giá trị lớn hơn ở bên phải. Tiếp theo, phần bên phải và bên trái cũng được chọn bởi phần tử hỗ trợ 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ử hỗ trợ được chọn từ các phần kết quả - v.v. hàng ngang. Thuật toán này trong Java được triển khai bằng cách 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 выхода из рекурсии,  если длина массива равна 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);
   }
}

Không còn nghi ngờ gì nữa, thuật toán quicksort được coi 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, trong thời gian O(N*logN) .

Hợp nhất sắp xếp

Cách sắp xếp này cũng phổ biến. Nó đề cập đến một trong những loại thuật toán hoạt động theo nguyên tắc “phân chia và chinh phục”: trong đó trước tiên chúng tôi chia nhiệm vụ thành các phần tối thiểu ( sắp xếp nhanh cũng là một đại diện của các thuật toán đó ). Vậy bản chất của thuật toán này là gì?

Chia:

Mảng được chia thành hai phần có kích thước gần bằng nhau, mỗi phần trong số hai phần này được chia thành hai phần nữa, v.v. cho đến khi còn lại những phần nhỏ nhất không thể chia được. Phần ít nhất không thể chia được là khi mỗi mảng có một phần tử, điều đó có nghĩa là mảng đó tự động được coi là đã sắp xếp.

Chinh phục:

Đây là nơi quá trình bắt đầu đặt tên cho thuật toán - hợp nhất . Để thực hiện việc này, hãy lấy hai mảng có thứ tự thu được 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ả và thao tác này được lặp lại cho đến khi không còn phần tử nào trong hai mảng. Nghĩa là, nếu chúng ta có hai mảng tối thiểu {6} và {4} , giá trị của chúng sẽ được so sánh và kết quả sẽ ghi: {4,6} . Nếu có các mảng được sắp xếp {4,6} và {2,8} thì trước tiên giá trị 4 và 2 sẽ được so sánh , trong đó 2 giá trị sẽ được ghi vào mảng kết quả. Sau đó, 4 và 8 sẽ được so sánh , 4 sẽ được viết ra và cuối cùng 6 và 8 sẽ được so sánh . Theo đó, 6 sẽ được viết và chỉ sau nó - 8. Kết quả là chúng ta sẽ nhận được mảng kết quả: {2,4,6,8} . Điều này sẽ trông như thế nào trong mã Java? Để xử lý 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);// массив для сортировки
       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;
   }
}

Giống như trong sắp xếp nhanh, chúng tôi chuyển phương thức đệ quy sang phương thức trung gian để người dùng không cần phải thiết lập các đối số mặc định bổ sung mà chỉ cần chỉ định mảng cần sắp xếp. Vì thuật toán này tương tự như thuật toán xóa nhanh hơn nên tốc độ thực thi 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 đưa ra các quyết định tối ưu cục bộ ở mỗi giai đoạn và 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” là giải pháp mang lại lợi ích rõ ràng và tức thời nhất ở một bước/giai đoạn nhất định. Để xem xét thuật toán này, hãy chọn một bài toán khá phổ biến - về một chiếc ba lô. Hãy giả vờ một chút 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ô và trước mặt bạn có một số hàng hóa mà bạn có thể lấy cắp. Nhưng đồng thời, sức chứa của ba lô còn hạn chế - không quá 30 chiếc thông thường. Đồng thời, bạn muốn mang theo một bộ hàng hóa có giá trị lớn nhất sẽ vừa vặn trong ba lô của mình. Làm thế nào để bạn quyết định những gì để đưa vào? Vì vậy, thuật toán tham lam cho bài toán chiếc ba lô bao gồm các bước sau (chúng tôi giả định rằng tất cả các đồ vật đều vừa với chiếc ba lô):

1. Chọn món đồ đắt tiền nhất trong số những món đồ chưa được chạm tới.
2. Nếu nó vừa với ba lô của bạn, hãy đặt nó ở đó; nếu không, hãy bỏ qua.
3. Bạn đã sắp xếp qua tất cả các mục? Nếu không, chúng ta quay lại điểm 1, nếu có, chúng ta chạy khỏi cửa hàng, vì mục tiêu của chúng ta ở đây đã hoàn thành.

Hãy xem xét điều này, nhưng bằng Java. Lớp Item sẽ trông như thế này:

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;
   }
}

Không có gì đặc biệt ở đây: ba trường - tên , trọng lượng , giá thành - để chỉ đị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 Comparable được triển khai ở đây để chúng ta có thể sắp xếp các Mặt hàng theo giá. Tiếp theo chúng ta xem xét lớp ba lô của chúng ta - Túi :

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 là dung lượng của chiếc ba lô của chúng ta, được thiết lập khi tạo đối tượng;
• đồ vật - đồ vật trong ba lô;
• currentWeight , currentCost - trọng lượng và chi phí hiện tại của tất cả mọi thứ trong ba lô mà chúng ta tăng lên khi thêm một mục mới trong phương thức addItem .

Thực ra, chúng ta hãy đến lớp, nơi tất cả các hành động diễn ra:

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());
}
}

Đầu tiên, chúng ta tạo một danh sách các phần tử và sắp xếp nó. Tạo một đối tượng túi có sức chứa 30 đơn vị. Tiếp theo, chúng ta gửi các phần tử và đối tượng túi tới phương thức fillBackpack , trong đó, trên thực tế, chiếc ba lô được lấp đầy bằng thuật toán tham lam:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

Mọi thứ cực kỳ đơn giản: chúng ta bắt đầu xem qua danh sách các món đồ được sắp xếp theo giá thành và cho vào túi, nếu sức chứa cho phép. Nếu không cho phép, phần tử sẽ bị bỏ qua và việc duyệt qua các phần tử còn lại sẽ tiếp tục cho đến cuối danh sách. Bằng cách chạy main, chúng ta nhận được kết quả sau trên console: Trên thực tế, đâ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 nhận được 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 tiền nhất. Nhưng đây có phải là giải pháp tốt nhất? Bạn không nghĩ rằng chúng ta có thể hiện đại hóa giải pháp của mình một chút để có thể trang bị một chiếc ba lô với tổng chi phí cao hơn sao? 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<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());
       }
   }
}

Ở đây trước tiên chúng tôi tính toán tỷ lệ trọng lượng-giá cho từng mặt hàng. Vì vậy, có thể nói, một đơn vị của một mặt hàng nhất định có giá bao nhiêu? Và theo những giá trị này, chúng tôi 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 mình. Hãy chạy:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

Chúng tôi nhận được đầu ra cho bàn điều khiển: 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 với kỳ vọng rằng giải pháp cuối cùng cũng sẽ tối ưu. Điều này không phải lúc nào cũng hợp lý, nhưng đối với nhiều vấn đề, thuật toán tham lam mang lại kết quả tối ưu. Độ phức tạp về thời gian của thuật toán này là O(N) , khá tốt phải không? Vậy là phần đầu tiên của bài viết này đã kết thúc. Nếu bạn quan tâm đến phần tiếp theo của bài viết này, bài viết sẽ nói về các biểu đồ và thuật toán liên quan đến chúng, bạn có thể tìm thấy nó ở đây .