Ide dasar algoritma serakah
1. Buat model matematika untuk menggambarkan masalah.
2. Bagilah masalah yang diselesaikan menjadi beberapa sub-masalah.
3. Selesaikan setiap sub-masalah dan dapatkan solusi optimal lokal untuk sub-masalah.
4. Sintesis solusi optimal lokal dari sub-masalah menjadi solusi untuk solusi asli dari masalah.
Proses menerapkan algoritma ini:
Mulai dari solusi awal tertentu ke masalah;
Sementara dapat bergerak maju ke tujuan keseluruhan yang diberikan
Temukan elemen solusi dari solusi yang layak;
Solusi yang layak untuk masalah terdiri dari semua elemen solusi.
Sifat selektif yang serakah
Nature seleksi serakah berarti bahwa solusi optimal keseluruhan dari masalah yang Anda cari dapat dicapai melalui serangkaian pilihan optimal lokal. Masalah saat ini tanpa mempertimbangkannya. Ini adalah elemen dasar pertama dari kelayakan algoritma serakah.
Algoritma serakah membuat pilihan serakah secara iteratif, dan setiap kali pilihan serakah dibuat, masalah yang Anda cari direduksi menjadi sub-masalah yang lebih kecil.
Untuk masalah tertentu, untuk menentukan apakah ia memiliki sifat pilihan serakah, perlu untuk membuktikan bahwa pilihan serakah yang dibuat pada setiap langkah pada akhirnya mengarah pada solusi optimal keseluruhan untuk masalah tersebut.
2. Properti Substruktur Optimal <BR /> Ketika solusi optimal dari suatu masalah berisi solusi optimal dari sub-masalahnya, masalah ini dikatakan memiliki sifat sub-struktural yang optimal. Sifat substruktur optimal dari masalah ini adalah fitur utama yang dapat diselesaikan dengan algoritma serakah.
Proses Umum Keserakahan
Salinan kode adalah sebagai berikut:
Serakah (c) // c adalah set input masalah, yaitu set kandidat
{
S = {}; // Solusi awal adalah set kosong
Sedangkan (bukan solusi) // set S bukan merupakan solusi untuk masalah
{
X = SELECT (C); // Buat pilihan serakah di kandidat set
Jika layak (s, x) // menilai apakah solusi setelah menambahkan x ke set s layak
S = s+{x};
C = c- {x};
}
kembali S;
Deskripsi Masalah:
Saat ini, ada koin dengan nilai wajah 2 Jiao 5 sen, 1 Jiao 5 sen, 5 sen dan 1 sen.
Analisis Masalah:
Menurut akal sehat, ketika kita pergi ke toko untuk membeli barang dan menemukan uang, bos selalu memberi kita denominasi maksimum terlebih dahulu. Jika bos meminta Anda untuk skor atau beberapa sen, Anda pasti tidak akan melakukannya. Bahkan, ini adalah masalah khas pilihan serakah.
Desain algoritma dan implementasi masalah :
Izinkan saya memberi Anda contoh terlebih dahulu. Dia mencarinya seperti ini? 'T LAKUKAN, maka bos hanya bisa memberi saya saya mendapat 3 25 poin dan saya diberi 24 lebih sedikit, jadi saya harus memberi saya 2 10 poin dan 4 1 poin.
Salinan kode adalah sebagai berikut:
// aritmatika untuk menemukan perubahan
// Input: Array M, Simpan jumlah nilai wajah yang diatur dari besar ke kecil secara berurutan.
// output: array num, bandingkan jumlah koin dengan nilai denominasi yang berbeda dalam array m, dan temukan paket uang
Public Static Int [] Zhaoqian (int m [], int n)
{
int k = m.length;
int [] num = int int [k];
untuk (int i = 0; i <k; i ++)
{
num <i> = n/m <i>;
n = n%m <i>;
}
Return Num;
}
Salinan kode adalah sebagai berikut:
Kelas Publik Zhaoqian
{
public static void main (string [] args)
{
int m [] = {25,10,5,1};
int n = 99;
int [] num = int int [m.length];
num = zhaoqian (m, n);
System.out.println (n+"Rencana Penemuan Uang:");
untuk (int i = 0; i <m.length; i ++)
System.out.println (num <i>+"zip"+m <i>+"nilai nominal");
}
Public Static Int [] Zhaoqian (int m [], int n)
{
int k = m.length;
int [] num = int int [k];
untuk (int i = 0; i <k; i ++)
{
num <i> = n/m <i>;
n = n%m <i>;
}
Return Num;
}
}
Di atas adalah semua konten dari artikel ini, saya harap Anda bisa menyukainya.