Bagaimana untuk melaksanakan algoritma tamak menggunakan Python?

Bagaimana untuk melaksanakan algoritma tamak menggunakan Python?

Algoritma Greedy ialah algoritma yang mudah dan berkesan sesuai untuk menyelesaikan masalah dengan sifat substruktur yang optimum. Ia memerlukan pilihan terbaik dalam keadaan semasa dalam setiap langkah pemilihan, dengan harapan dapat mencari penyelesaian optimum global. Dalam artikel ini, kami akan memperkenalkan cara menggunakan Python untuk melaksanakan algoritma tamak, dengan contoh kod tertentu.

1. Idea asas algoritma tamak

Idea asas algoritma tamak adalah untuk memilih penyelesaian optimum dalam keadaan semasa pada setiap langkah, dan kemudian meneruskan ke langkah seterusnya. Algoritma tamak bukan algoritma yang boleh menyelesaikan semua masalah, tetapi sesuai untuk beberapa masalah dengan sifat pemilihan tamak. Masalah ini mempunyai dua ciri berikut:

1. Substruktur optimum: Penyelesaian optimum masalah boleh diperoleh daripada penyelesaian optimum sub-masalah.
2. Harta pilihan tamak: Penyelesaian optimum yang dipilih pada setiap langkah adalah pilihan terbaik dalam keadaan semasa, iaitu penyelesaian optimum tempatan.

Berdasarkan dua ciri ini, apabila menggunakan algoritma tamak, anda perlu memberi perhatian sama ada masalah itu memenuhi sifat substruktur yang optimum dan secara munasabah memilih penyelesaian optimum untuk setiap langkah.

2. Langkah-langkah pelaksanaan algoritma tamak

Langkah pelaksanaan algoritma tamak biasanya termasuk langkah-langkah berikut:

1. Tentukan sifat pemilihan tamak masalah.
2. Uraikan masalah kepada beberapa sub-masalah.
3. Reka bentuk algoritma tamak untuk menyelesaikan setiap sub-masalah dan mendapatkan penyelesaian optimum setempat.
4. Gabungkan penyelesaian optimum tempatan ke dalam penyelesaian keseluruhan masalah.

3. Contoh penggunaan Python untuk melaksanakan algoritma tamak

Berikut mengambil masalah perubahan sebagai contoh untuk menunjukkan cara menggunakan Python untuk melaksanakan algoritma tamak.

Soalan: Katakan terdapat wang kertas 1 yuan, 2 yuan, 5 yuan, 10 yuan, 20 yuan, 50 yuan dan 100 yuan, dan bilangan perubahan yang diperlukan untuk memberi pelanggan ialah n yuan, cara menggunakan minimum bilangan wang kertas untuk menukar pelanggan pelanggan?

Idea pelaksanaan:

1. Tentukan sifat pemilihan tamak masalah: Dalam masalah perubahan, wang kertas dengan denominasi terbesar harus dipilih setiap kali semasa membuat perubahan.
2. Uraikan masalah kepada beberapa sub-masalah: setiap kali anda memberikan perubahan, ia adalah sub-masalah, dan denominasi perubahan terus berkurangan.
3. Reka bentuk algoritma tamak untuk menyelesaikan setiap sub-masalah dan dapatkan penyelesaian optimum setempat: pilih wang kertas dengan denominasi terbesar setiap kali anda membuat perubahan sehingga bilangan perubahan ialah 0.
4. Gabungkan penyelesaian optimum tempatan ke dalam penyelesaian keseluruhan kepada masalah: Tambahkan setiap penyelesaian optimum tempatan untuk mendapatkan bilangan wang kertas minimum.

Berikut ialah contoh kod khusus menggunakan Python untuk melaksanakan algoritma tamak untuk menyelesaikan masalah perubahan:

def make_change(n):
    denominations = [100, 50, 20, 10, 5, 2, 1]
    count = 0
    
    for denomination in denominations:
        count += n // denomination
        n = n % denomination
        
    return count

# 测试示例
print(make_change(47))  # 输出结果为4，使用1个20元、2个2元和1个1元
print(make_change(123)) # 输出结果为6，使用1个100元、1个20元和3个1元

Dalam kod di atas, fungsi make_change menerima integer n sebagai parameter, menunjukkan bilangan perubahan yang diperlukan. Pertama, tentukan senarai denominasi denominasi wang kertas, disusun mengikut tertib daripada terbesar kepada terkecil. Kemudian, gunakan gelung for untuk mengulangi setiap denominasi dan hitung bilangan nota yang diperlukan dan jumlah yang tinggal. Akhir sekali, kembalikan bilangan kiraan wang kertas.

Melalui contoh di atas, kami menunjukkan cara menggunakan Python untuk melaksanakan algoritma tamak untuk menyelesaikan masalah perubahan. Langkah-langkah pelaksanaan algoritma tamak adalah untuk menentukan sifat pemilihan tamak masalah, menguraikan masalah kepada beberapa sub-masalah, mereka bentuk algoritma tamak untuk menyelesaikan setiap sub-masalah dan menggabungkan penyelesaian optimum tempatan.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma tamak menggunakan Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!