Bagaimana untuk melaksanakan penyelesaian yang cekap kepada masalah perubahan syiling paling sedikit dalam PHP menggunakan algoritma tamak?

Bagaimana untuk melaksanakan penyelesaian yang cekap kepada masalah penukaran syiling paling sedikit dalam PHP menggunakan algoritma tamak?

Petikan:
Dalam kehidupan seharian, kita selalunya perlu melakukan perubahan terutama ketika berbelanja atau berniaga. Untuk menggunakan seberapa sedikit syiling yang mungkin, amaun perubahan hendaklah digabungkan menggunakan seberapa sedikit syiling yang mungkin. Dalam pengaturcaraan komputer, kita boleh menggunakan algoritma tamak untuk menyelesaikan masalah ini untuk mendapatkan penyelesaian yang cekap. Artikel ini menerangkan cara melaksanakan penyelesaian yang cekap kepada masalah penukaran syiling minimum menggunakan algoritma tamak dalam PHP dan menyediakan contoh kod yang sepadan.

1. Prinsip Algoritma Greedy
   Algoritma tamak ialah idea untuk menyelesaikan masalah Ia memilih penyelesaian optimum semasa pada setiap langkah dan akhirnya memperoleh penyelesaian optimum global. Dalam masalah penukaran syiling minimum, idea algoritma tamak adalah untuk memilih syiling dengan denominasi terbesar kurang daripada atau sama dengan jumlah sasaran untuk membuat perubahan setiap kali sehingga semua syiling ditemui.
2. Penyelesaian kepada masalah penukaran syiling minimum
   Berikut adalah langkah-langkah untuk menggunakan algoritma tamak untuk menyelesaikan masalah penukaran syiling minimum dalam PHP:

Langkah 1: Buat fungsi bernama minimumCoins yang menerima dua parameter: jumlah (jumlah ) dan susunan denominasi syiling (syiling).
Langkah 2: Tentukan tatasusunan hasil kosong (hasil) untuk menyimpan gabungan syiling untuk perubahan.
Langkah 3: Isih tatasusunan denominasi syiling dalam tertib menurun untuk memilih syiling dengan denominasi yang lebih besar daripada besar ke kecil.
Langkah 4: Lintas tatasusunan denominasi syiling dan pilih syiling yang denominasi semasanya kurang daripada atau sama dengan jumlah sasaran setiap kali untuk membuat perubahan.
Langkah 5: Semasa proses perubahan, kemas kini jumlah sasaran, tambahkan denominasi syiling yang dipilih pada tatasusunan hasil dan tolak denominasi syiling yang dipilih daripada jumlah sasaran.
Langkah 6: Ulang langkah 4 dan 5 sehingga jumlah sasaran ialah 0.
Langkah 7: Kembalikan tatasusunan hasil.

Berikut ialah contoh kod PHP khusus:

function minimumCoins($amount, $coins) {
    $result = []; // 存储找零的硬币组合
    rsort($coins); // 降序排列硬币面额数组
    
    foreach ($coins as $coin) {
        while ($coin <= $amount) {
            $result[] = $coin; // 将当前硬币面额添加到结果数组中
            $amount -= $coin; // 更新目标金额
        }
    }
    
    return $result;
}

$amount = 47; // 目标金额
$coins = [25, 10, 5, 1]; // 硬币面额数组
$result = minimumCoins($amount, $coins);

echo "找零组合：";
foreach ($result as $coin) {
    echo $coin . " ";
}

Kod di atas akan mengeluarkan: "Tukar kombinasi: 25 10 10 1 1", iaitu, 5 syiling diperlukan untuk membuat perubahan 47 yuan.

3. Kerumitan Masa dan Kerumitan Ruang
   Kerumitan masa untuk menyelesaikan masalah perubahan syiling minimum menggunakan algoritma tamak ialah O(n), di mana n ialah bilangan denominasi syiling. Kerumitan ruang ialah O(1) kerana hanya ruang tambahan yang berterusan diperlukan untuk menyimpan hasilnya.

Kesimpulan:
Dengan menggunakan algoritma tamak, kami boleh menyelesaikan masalah penukaran syiling minimum dalam PHP dengan cekap. Masalah ini sangat praktikal dalam kehidupan seharian, dan algoritma tamak menyediakan penyelesaian yang mudah dan cekap. Saya harap contoh kod dan idea penyelesaian yang disediakan dalam artikel ini akan membantu anda.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan penyelesaian yang cekap kepada masalah perubahan syiling paling sedikit dalam PHP menggunakan algoritma tamak?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!