Untuk Contoh Permasalahan yang Kalian Pilih Sebagai Jawaban di No. 1

-

Untuk contoh permasalahan yang kalian pilih sebagai jawaban di no. 1, menurut kalian apakah algoritma greedy dapat diterapkan pada permasalahan tersebut?

Jawaban:

Untuk contoh permasalahan yang saya pilih sebagai jawaban di no. 1, menurut saya algoritma greedy dapat diterapkan pada permasalahan tersebut.

Sebuah contoh permasalahan optimasi yang dapat diterapkan dengan menggunakan algoritma serakah (greedy algorithm) adalah permasalahan kembalian uang).

Permasalahan ini berkaitan dengan cara memberikan kembalian uang dengan jumlah lembaran paling sedikit.

Misalkan Anda harus memberikan kembalian sejumlah uang tertentu menggunakan sejumlah uang pecahan yang tersedia. Tugasnya adalah menentukan kombinasi pecahan yang paling sedikit untuk mencapai jumlah kembalian tersebut.

Misalnya, Anda perlu memberikan kembalian sebesar 78 ribu rupiah dengan pecahan-pecahan koin atau lembaran yang tersedia: 50 ribu, 20 ribu, 10 ribu, 5 ribu, dan 1 ribu.

Dalam hal ini, algoritma serakah dapat diterapkan dengan cara berikut:

1. Urutkan pecahan-pecahan uang dalam urutan menurun.
Misalnya: 50 ribu, 20 ribu, 10 ribu, 5 ribu, 1 ribu.

2. Inisialisasikan jumlah pecahan yang diperlukan untuk kembalian menjadi 0.

3. Mulai dari pecahan uang terbesar, hitung jumlah pecahan uang yang diperlukan dengan cara berikut:
  • Bagi jumlah kembalian dengan pecahan uang tersebut (tanpa memperhatikan sisa).
  • Tambahkan jumlah pecahan uang yang diperlukan dengan hasil pembagian tersebut.
  • Perbarui jumlah kembalian dengan sisa hasil bagi.
4. Ulangi langkah 3 untuk pecahan uang yang lebih kecil, dan terus lanjutkan hingga mencapai pecahan uang terkecil.

5. Jumlah pecahan uang yang diperlukan adalah total dari semua pecahan uang.

Berikut adalah contoh penerapan algoritma serakah pada permasalahan kembalian uang dengan pecahan-pecahan yang diberikan:

1. Urutan pecahan: 50 ribu, 20 ribu, 10 ribu, 5 ribu, 1 ribu.
2. Inisialisasi jumlah pecahan uang: 0.

Mulai dengan pecahan uang 50 ribu:
  • Bagi 78 ribu dengan 50 ribu = 1 (tanpa sisa).
  • Tambahkan 1 ke jumlah pecahan uang: 0 + 1 = 1.
  • Perbarui jumlah kembalian dengan sisa: 78 ribu - (1 x 50 ribu) = 28 ribu.

Lanjutkan dengan pecahan uang 20 ribu:
  • Bagi 28 ribu dengan 20 ribu = 1 (tanpa sisa).
  • Tambahkan 1 ke jumlah pecahan uang: 1 + 1 = 2.
  • Perbarui jumlah kembalian dengan sisa: 28 ribu - (1 x 20 ribu) = 8 ribu.

Lanjutkan dengan pecahan uang 10 ribu:
  • Bagi 8 ribu dengan 10 ribu = 0 (tanpa sisa).
  • Tidak ada penambahan pada jumlah pecahan uang.
  • Jumlah kembalian tetap 8 ribu.

Lanjutkan dengan pecahan uang 5 ribu:
  • Bagi 8 ribu dengan 5 ribu = 1 (tanpa sisa).
  • Tambahkan 1 ke jumlah pecahan uang: 2 + 1 = 3.
  • Perbarui jumlah kembalian dengan sisa: 8 ribu - (1 x 5 ribu) = 3 ribu.

Terakhir, pecahan uang 1 ribu:
  • Bagi 3 ribu dengan 1 ribu = 3 (tanpa sisa).
  • Tambahkan 3 ke jumlah pecahan uang: 3 + 3 = 6.

Jadi, untuk memberikan kembalian sebesar 78 ribu rupiah dengan pecahan-pecahan yang diberikan, diperlukan minimal 6 pecahan uang.