Perkara yang mereka tanya semasa temu bual: semakan algoritma, bahagian 1

Selamat tengahari semua! Pelbagai jenis algoritma digunakan dalam projek lebih kerap daripada yang anda fikirkan. Sebagai contoh, kita perlu mengisih beberapa data mengikut parameter tertentu (lajur) supaya kita boleh menavigasi melaluinya tanpa banyak usaha. Oleh itu, tidak ada yang aneh dalam fakta bahawa semasa temu duga kerja mereka mungkin ditanya tentang satu atau lain algoritma asas, dan mungkin diberi tugas untuk melaksanakannya menggunakan kod. Dan kerana anda berada di laman web ini, saya akan cuba meneka bahawa anda menulis dalam Java. Oleh itu, hari ini saya menjemput anda untuk membiasakan diri dengan beberapa algoritma asas dan contoh khusus pelaksanaannya di Jawa. Oleh beberapa yang saya maksudkan:

1. Gambaran keseluruhan algoritma pengisihan tatasusunan:
   • jenis gelembung,
   • jenis pemilihan,
   • jenis sisipan,
   • Jenis cangkang,
   • susun cepat,
   • merge sort.
2. Algoritma tamak.
3. Algoritma pencarian laluan:
   • merangkak secara mendalam
   • berjalan lebar.
4. Algoritma pengangkutan ialah algoritma Dijkstra.

Nah, tanpa berlengah lagi, mari kita mula berniaga.

1. Gambaran keseluruhan algoritma pengisihan

Isih gelembung

Algoritma pengisihan ini dikenali terutamanya kerana kesederhanaannya, tetapi ia juga mempunyai salah satu kelajuan pelaksanaan yang paling rendah. Sebagai contoh, pertimbangkan isihan gelembung untuk nombor dalam tertib menaik. Mari bayangkan rangkaian nombor yang diletakkan secara rawak yang mana langkah-langkah berikut akan dilakukan, bermula dari permulaan rantaian:

• bandingkan dua nombor;
• jika nombor di sebelah kiri lebih besar, maka tukarkannya;
• gerakkan satu kedudukan ke kanan.

Selepas melalui keseluruhan rantaian dan melakukan langkah-langkah ini, kami akan mendapati bahawa nombor terbesar berada di penghujung siri nombor kami. Seterusnya, laluan yang sama di sepanjang rantai dilakukan, mengikut langkah yang diterangkan di atas. Tetapi kali ini kami tidak akan memasukkan elemen terakhir senarai, kerana ia adalah yang terbesar dan sudah berada di tempat terakhir, seperti yang sepatutnya. Sekali lagi, kami akan mendapat elemen terakhir pada penghujung siri nombor kami yang dipersoalkan. Sehubungan itu, dua nombor terbesar sudah pun berada di tempat mereka. Dan sekali lagi laluan di sepanjang rantai dimulakan, tidak termasuk unsur-unsur yang sudah ada, sehingga semua elemen berada dalam susunan yang diperlukan. Mari kita lihat pelaksanaan jenis gelembung dalam kod 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;
             }
         }
       }
   }
}

Seperti yang anda lihat, tiada apa-apa yang rumit di sini, dan segala-galanya nampaknya hebat, jika bukan untuk satu "tetapi"... Isih gelembung sangat, sangat perlahan, dengan kerumitan masa O(N²) , kerana kami telah bersarang gelung. Lulus luaran melalui elemen dilakukan dalam N kali, yang dalaman juga N kali, dan hasilnya kami mendapat N*N , lelaran N² . Anda boleh mengkaji jenis pengisihan ini dengan lebih terperinci dalam artikel ini .

Isih mengikut pilihan

Algoritma ini serupa dengan jenis gelembung, tetapi ia berfungsi lebih pantas sedikit. Sekali lagi, sebagai contoh, mari kita ambil satu siri nombor yang ingin kita susun dalam tertib menaik. Intipati algoritma adalah untuk memeriksa semua nombor secara berurutan dan memilih elemen terkecil, yang kami ambil dan menukar tempat dengan elemen paling kiri (0 elemen). Di sini kita mendapat situasi yang serupa dengan jenis gelembung, tetapi dalam kes ini elemen yang diisih akan menjadi yang terkecil. Oleh itu, laluan seterusnya melalui elemen akan bermula dengan elemen pada indeks 1. Sekali lagi, laluan ini akan diulang sehingga semua elemen diisih. Pelaksanaan di Jawa:

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

Algoritma ini lebih baik daripada jenis gelembung, kerana di sini bilangan pilih atur yang diperlukan dikurangkan daripada O(N²) kepada O(N): kami tidak menolak satu elemen melalui keseluruhan senarai, tetapi bagaimanapun, bilangan perbandingan kekal O(N² ) . Bagi mereka yang ingin mengetahui lebih lanjut tentang algoritma ini, saya mengesyorkan bahan ini .

Isihan sisipan

Sekali lagi, sebagai contoh, mari kita ambil satu siri nombor yang ingin kita susun dalam tertib menaik. Algoritma ini terdiri daripada meletakkan penanda, di sebelah kiri elemen-elemen itu akan diisih sebahagiannya di antara mereka. Pada setiap langkah algoritma, salah satu elemen akan dipilih dan diletakkan pada kedudukan yang dikehendaki dalam urutan yang telah disusun. Jadi bahagian yang disusun akan terus berkembang sehingga semua elemen telah dilihat. Anda mungkin bertanya: di manakah saya boleh mendapatkan bahagian elemen yang telah disusun dan selepas itu anda perlu meletakkan penanda? Tetapi susunan elemen pertama sudah disusun, bukan? Mari kita lihat pelaksanaan di Jawa:

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;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Pengisihan jenis ini lebih baik daripada yang diterangkan di atas, kerana walaupun pada hakikatnya masa berjalan adalah sama - O(N²) , algoritma ini berfungsi dua kali lebih pantas daripada isihan gelembung dan lebih pantas sedikit daripada isihan pemilihan. Baca lebih lanjut di sini .

Isih cangkerang

Jenis ini, mengikut sifatnya, ialah jenis sisipan yang diubah suai. Apa yang saya cakapkan? Jom ikut tertib. Satu langkah dipilih, dan terdapat banyak pendekatan untuk pilihan ini. Kami tidak akan membincangkan isu ini secara terperinci. Mari bahagikan tatasusunan kami kepada separuh dan dapatkan nombor tertentu - ini akan menjadi langkah kami. Jadi, jika kita mempunyai 9 elemen dalam tatasusunan, maka langkah kita ialah 9/2 = 4.5 . Kami membuang bahagian pecahan dan mendapat 4 , kerana indeks tatasusunan hanyalah integer. Dengan langkah ini kami akan membuat sambungan untuk kumpulan kami. Jika sesuatu elemen mempunyai indeks 0, maka indeks unsur seterusnya dalam kumpulannya ialah 0+4 , iaitu 4 . Unsur ketiga akan mempunyai indeks 4+4 , unsur keempat akan mempunyai indeks 8+4 dan seterusnya. Untuk kumpulan kedua, elemen pertama ialah 1,5,9…. Dalam kumpulan ketiga dan keempat, perkara akan sama. Hasilnya, daripada tatasusunan nombor {6,3,8,8,6,9,4,11,1} kita mendapat empat kumpulan: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Mereka mengekalkan tempat mereka dalam tatasusunan umum, tetapi bagi kami mereka ditandakan sebagai ahli kumpulan yang sama: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Selanjutnya dalam kumpulan ini jenis sisipan , selepas itu kumpulan akan kelihatan seperti: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Dalam tatasusunan umum, sel yang diduduki oleh kumpulan , akan kekal sama, tetapi susunan di dalamnya akan berubah, mengikut susunan kumpulan di atas: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Tatasusunan sedikit lebih teratur, bukan? Langkah seterusnya akan dibahagikan dengan 2: 4/2 = 2 Kami mempunyai dua kumpulan: I - {1,4,6,8,6} II - {3,8,9,11} B tatasusunan umum: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Kami melalui kedua-dua kumpulan menggunakan algoritma isihan sisipan dan mendapatkan tatasusunan: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Kini tatasusunan kami hampir diisih. Lelaran terakhir algoritma kekal: kami membahagikan langkah dengan 2: 2/2 = 1. Kami mendapat kumpulan, keseluruhan tatasusunan: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Mengikut yang kita lalui algoritma isihan sisipan dan dapatkan : { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Mari lihat bagaimana kita boleh memaparkan pengisihan ini dalam kod 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; // уменьшаем наш шаг
       }
   }
}

Pada masa ini, keberkesanan pengisihan Shell tidak benar-benar terbukti, kerana hasilnya berbeza dalam situasi yang berbeza. Anggaran yang diperoleh daripada eksperimen berjulat dari O(N ^3/2 ) hingga O(N ^7/6 ) .

Isih cepat

Ini adalah salah satu algoritma yang paling popular, dan oleh itu ia patut diberi perhatian khusus. Intipati algoritma ini ialah elemen pangsi dipilih daripada senarai elemen—pada asasnya mana-mana elemen yang mana nilai selebihnya perlu diisih. Nilai kurang daripada di sebelah kiri, nilai lebih besar daripada di sebelah kanan. Seterusnya, bahagian kanan dan kiri juga dipilih oleh elemen sokongan dan perkara yang sama berlaku: nilai diisih relatif kepada unsur-unsur ini, kemudian elemen sokongan dipilih dari bahagian yang dihasilkan - dan seterusnya sehingga kita mendapat disusun. barisan. Algoritma ini dalam Java dilaksanakan menggunakan rekursi:

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

Tidak syak lagi, algoritma quicksort dianggap paling popular, kerana dalam kebanyakan situasi ia berjalan lebih pantas daripada yang lain, dalam masa O(N*logN) .

Gabungkan jenis

Pengisihan ini juga popular. Ia merujuk kepada salah satu jenis algoritma yang bekerja pada prinsip "bahagi dan takluk": di dalamnya kita mula-mula membahagikan tugas kepada bahagian yang minimum ( jenis cepat juga mewakili algoritma sedemikian ). Jadi, apakah intipati algoritma ini?

Bahagikan:

Tatasusunan dibahagikan kepada dua bahagian yang lebih kurang sama saiznya, setiap satu daripada dua bahagian ini dibahagikan kepada dua lagi, dan seterusnya sehingga bahagian terkecil yang tidak boleh dibahagikan kekal. Bahagian yang paling tidak boleh dibahagikan ialah apabila setiap tatasusunan mempunyai satu elemen, yang bermaksud tatasusunan sedemikian dianggap diisih secara automatik.

Menakluk:

Di sinilah proses bermula yang memberikan nama kepada algoritma - penggabungan . Untuk melakukan ini, ambil dua tatasusunan yang terhasil dan gabungkannya menjadi satu. Dalam kes ini, elemen pertama yang terkecil daripada dua tatasusunan ditulis pada tatasusunan yang terhasil, dan operasi ini diulang sehingga tiada lagi elemen dalam dua tatasusunan. Iaitu, jika kita mempunyai dua tatasusunan minimum {6} dan {4} , nilainya akan dibandingkan dan hasilnya akan ditulis: {4,6} . Jika terdapat tatasusunan yang diisih {4,6} dan {2,8} , maka nilai 4 dan 2 akan dibandingkan dahulu , yang mana 2 daripadanya akan ditulis pada tatasusunan yang terhasil. Selepas ini, 4 dan 8 akan dibandingkan , 4 akan ditulis, dan pada akhir 6 dan 8 akan dibandingkan . Sehubungan itu, 6 akan ditulis, dan hanya selepas itu - 8. Hasilnya, kita akan mendapat tatasusunan yang terhasil: {2,4,6,8} . Bagaimanakah ini akan kelihatan dalam kod Java? Untuk memproses algoritma ini, adalah mudah bagi kami untuk menggunakan rekursi:

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

Seperti dalam isihan pantas, kami mengalihkan kaedah rekursif kepada kaedah perantaraan supaya pengguna tidak perlu bersusah payah menetapkan argumen lalai tambahan, tetapi hanya boleh menentukan tatasusunan yang perlu diisih. Memandangkan algoritma ini serupa dengan pemadaman yang lebih pantas, kelajuan pelaksanaannya adalah sama - O(N*logN) .

2. Algoritma Tamak

Algoritma tamak ialah pendekatan yang mengambil keputusan optimum tempatan pada setiap peringkat dan menganggap bahawa penyelesaian akhir juga akan optimum. Penyelesaian "optimum" ialah penyelesaian yang menawarkan faedah yang paling jelas dan segera pada langkah/peringkat tertentu. Untuk mempertimbangkan algoritma ini, mari pilih masalah yang agak biasa - mengenai beg galas. Mari kita berpura-pura sebentar bahawa anda seorang pencuri. Anda memecah masuk kedai pada waktu malam dengan beg galas, dan di hadapan anda terdapat beberapa barang yang boleh anda curi. Tetapi pada masa yang sama, kapasiti beg galas adalah terhad - tidak lebih daripada 30 unit konvensional. Pada masa yang sama, anda ingin membawa satu set barang dengan nilai maksimum yang sesuai dengan beg galas anda. Bagaimana anda memutuskan apa yang perlu dimasukkan? Jadi, algoritma tamak untuk masalah ransel terdiri daripada langkah-langkah berikut (kami mengandaikan bahawa semua objek masuk ke dalam beg beg):

1. Pilih barang yang paling mahal daripada yang belum disentuh.
2. Jika ia muat dalam beg galas anda, letakkan di sana; jika tidak, langkau ia.
3. Adakah anda telah mengisih semua item? Jika tidak, kami kembali ke titik 1, jika ya, kami lari dari kedai, kerana matlamat kami di sini selesai.

Mari kita lihat ini, tetapi di Jawa. Inilah rupa kelas 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;
   }
}

Tiada apa yang istimewa di sini: tiga medan - nama , berat , kos - untuk menyatakan ciri item. Selain itu, seperti yang anda lihat, antara muka Sebanding dilaksanakan di sini supaya kami boleh mengisih Item kami mengikut harga. Seterusnya kita lihat kelas beg galas kita - Beg :

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 ialah kapasiti beg galas kami, yang ditetapkan semasa mencipta objek;
• barang — objek dalam beg galas;
• currentWeight , currentCost - berat semasa dan kos semua perkara dalam beg galas, yang kami tambah apabila menambah item baharu dalam kaedah addItem .

Sebenarnya, mari pergi ke kelas, di mana semua tindakan berlaku:

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

Pertama, kami membuat senarai elemen dan menyusunnya. Buat objek beg dengan kapasiti 30 unit. Seterusnya, kami menghantar elemen dan objek beg ke kaedah fillBackpack , di mana, sebenarnya, beg galas diisi menggunakan algoritma tamak:

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

Segala-galanya sangat mudah: kami mula menyemak senarai item yang disusun mengikut kos dan memasukkannya ke dalam beg, jika kapasiti membenarkan. Jika ia tidak membenarkan, elemen akan dilangkau dan laluan melalui elemen yang selebihnya akan diteruskan sehingga akhir senarai. Dengan menjalankan main, kami mendapat output berikut ke konsol: Sebenarnya, ini adalah contoh algoritma tamak: pada setiap langkah penyelesaian optimum tempatan dipilih, dan pada akhirnya anda mendapat penyelesaian optimum global. Dalam kes kami, pilihan terbaik adalah item yang paling mahal. Tetapi adakah ini penyelesaian terbaik? Tidakkah anda fikir kami boleh memodenkan sedikit penyelesaian kami supaya kami boleh melengkapkan beg galas dengan jumlah kos yang lebih tinggi? Mari kita lihat bagaimana ini boleh dilakukan:

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

Di sini kita mula-mula mengira nisbah berat-harga untuk setiap item. Jadi untuk bercakap, berapa kos satu unit item tertentu? Dan dengan nilai ini kami menyusun barang kami dan menambahkannya ke dalam beg kami. Jom lari:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

Kami mendapat output ke konsol: Lebih baik sedikit, bukan? Algoritma tamak membuat pilihan optimum tempatan pada setiap langkah dengan jangkaan bahawa penyelesaian akhir juga akan optimum. Ini tidak selalu wajar, tetapi untuk banyak masalah, algoritma tamak memberikan yang optimum. Kerumitan masa algoritma ini ialah O(N) , yang cukup bagus, bukan? Nah, dengan itu, bahagian pertama artikel ini telah berakhir. Jika anda berminat dengan kesinambungan artikel ini, yang akan bercakap tentang graf dan algoritma yang berkaitan dengannya, anda boleh menemuinya di sini .