Masalah penukaran koin

Kasir yang memberi kembalian mengambil koin terbesar yang muat, lalu yang berikutnya, dan untuk euro atau dolar cara itu selalu menghasilkan koin paling sedikit. Namun, jika koinnya diubah menjadi 1, 3, dan 4, kebiasaan yang sama membayar 6 dengan tiga koin padahal dua sudah cukup. Pemrograman dinamis menemukan minimum yang sebenarnya untuk koin apa pun.

Sederet jumlah, masing-masing dengan koin paling sedikit yang membentuknya, di atas koin-koin dengan tiga ukuran berbeda
Sederet jumlah, masing-masing dengan koin paling sedikit yang membentuknya, di atas koin-koin dengan tiga ukuran berbeda

Dua pertanyaan

Masalah penukaran koin hadir dalam dua bentuk. Yang pertama menanyakan koin paling sedikit yang membentuk jumlah yang tepat; ini juga disebut masalah pemberian kembalian. Yang kedua menanyakan berapa banyak kombinasi koin berbeda yang membentuknya. Pada keduanya, setiap jenis koin boleh dipakai berapa kali saja, dan keduanya diselesaikan dengan membangun jawaban untuk setiap jumlah dari jawaban untuk jumlah yang lebih kecil.

Koin paling sedikit, langkah demi langkah

Buat sederet sel untuk jumlah dari 0 sampai target. Jumlah 0 butuh 0 koin; setiap jumlah lain dimulai dari tak hingga. Telusuri jumlah-jumlah secara berurutan, dan untuk masing-masing coba setiap koin c yang muat: sel untuk jumlah dikurangi c, ditambah satu koin, adalah satu kandidat. Simpan yang terkecil. Setiap sel hanya bergantung pada sel di sebelah kirinya, yang sudah final, jadi satu kali penelusuran mengisi seluruh deret.

Sebuah contoh

Dengan koin 1, 3, dan 4: jumlah 1 butuh 1 koin, 2 butuh 2, 3 butuh 1 (satu koin 3), dan 4 butuh 1. Untuk 5, coba 1 (4 butuh 1, jadi 2 koin), 3 (2 butuh 2, jadi 3 koin), dan 4 (1 butuh 1, jadi 2 koin): yang terbaik 2. Untuk 6, coba 1 (5 butuh 2, jadi 3), 3 (3 butuh 1, jadi 2), dan 4 (2 butuh 2, jadi 3): yang terbaik 2, yaitu 3 + 3. Greedy akan membayar 4 + 1 + 1.

Menghitung banyaknya cara

Untuk menghitung kombinasi, tambahkan koin satu per satu. Dengan hanya koin pertama, setiap jumlah bisa dibentuk dengan satu cara atau tidak sama sekali. Saat koin baru c bergabung, cara membentuk jumlah a adalah cara lama, tanpa c, ditambah cara membentuk a − c dengan c boleh dipakai lagi, karena masing-masing cara itu menjadi cara membentuk a dengan menambahkan satu c lagi. Dengan koin 1, 2, dan 5 ada 4 cara membentuk 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1, dan 1 + 1 + 1 + 1 + 1.

Kapan greedy sudah cukup

Sistem koin yang membuat greedy selalu memberi koin paling sedikit disebut kanonik. Sebagian besar mata uang modern dirancang seperti itu, dan pada 1994 David Pearson menjelaskan sebuah uji yang memeriksa sistem koin dalam sejumlah langkah yang tumbuh hanya secara polinomial terhadap banyaknya koin. Koin Inggris lama tidak kanonik: greedy membayar 48 pence dengan satu half crown, satu shilling, dan satu sixpence, padahal dua florin sudah cukup.

Jelajahi sendiri

Buka aplikasinya, beralih ke tampilan Tabel, lalu tekan Langkah. Dalam mode Koin paling sedikit, sel oranye adalah jumlah yang sedang dihitung dan sel biru adalah jumlah lebih kecil yang tersisa setelah koin; baris di bawahnya menyimpan koin terakhir, dan pada akhirnya koin-koin dibaca mundur di sepanjang baris itu. Beralihlah ke Banyaknya cara dan lihat hitungannya bertambah baris demi baris saat setiap koin bergabung.

Pertanyaan yang sering diajukan

Apakah masalah penukaran koin termasuk masalah knapsack?

Kerabat dekat. Versi koin paling sedikit adalah masalah unbounded knapsack: setiap koin adalah barang dengan berat sama dengan nilai nominalnya, tas harus terisi tepat penuh, dan tujuannya adalah barang paling sedikit.

Berapa kompleksitas waktunya?

O(k·A) untuk k jenis koin dan jumlah A, pada kedua versi. Tabel untuk koin paling sedikit punya A + 1 sel, dan tabel untuk banyaknya cara (k + 1)·(A + 1) sel, meskipun satu baris sudah cukup jika sel diperbarui di tempat.

Mengapa koin dihitung dalam urutan tetap?

Jika setiap jumlah mencoba setiap koin, 1 + 2 dan 2 + 1 akan dihitung sebagai dua cara. Menambahkan koin satu baris demi satu baris berarti sebuah kombinasi selalu dibangun dari koin-koin yang lebih awal dulu, sehingga masing-masing dihitung tepat sekali.

Bisakah koin dibaca mundur untuk banyaknya cara?

Tidak sebagai satu jawaban, karena caranya banyak. Versi koin paling sedikit menyimpan koin terakhir dari setiap jumlah, dan itu cukup untuk membangun ulang satu kombinasi terbaik.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba penukaran koin