Koin terpakai
Jumlah terbentuk
Paling sedikit

    Koin (¢)

      Selengkapnya tentang masalah penukaran koin

      Masalah penukaran koin

      Dengan beberapa jenis koin, bagaimana membayar jumlah yang tepat dengan koin sesedikit mungkin, dan ada berapa cara melakukannya? Jawaban greedy, koin terbesar dulu, berhasil untuk uang sungguhan tetapi gagal untuk beberapa himpunan koin. Tabel yang membangun setiap jumlah dari jumlah yang lebih kecil selalu memberi jawaban yang benar. Ketuk koin di baki untuk menambahkannya ke meja, dan ketuk koin di meja untuk mengambilnya kembali. Meteran terisi menuju jumlah: bentuk jumlah itu dengan tepat, dengan koin sesedikit mungkin. Koin paling sedikit menunjukkan jawaban terbaik, dan Greedy menunjukkan hasilnya jika selalu mengambil koin terbesar yang muat, yang tidak selalu paling sedikit. Ubah koin (dalam sen) dan jumlah di panel. Tampilan Tabel menunjukkan cara pemrograman dinamis menemukan koin paling sedikit, atau menghitung banyaknya cara membentuk jumlah itu: tekan Putar untuk melihat tabel terisi, atau Langkah dan Mundur untuk bergerak satu langkah demi satu langkah, dan seret penggeser langkah untuk melompat ke mana saja. Setiap koin boleh dipakai sesering yang Anda mau. Saat tabel dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

      Cara kerjanya

      1. Ketuk koin di nampan untuk membentuk jumlahnya dengan tepat, dan lihat meteran terisi dalam sen.
      2. Coba gunakan koin sesedikit mungkin, lalu tekan Koin paling sedikit atau Greedy untuk membandingkan.
      3. Buka tampilan Tabel dan tekan Putar untuk melihat setiap sel membaca jumlah lebih kecil yang menjadi dasarnya.

      Koin paling sedikit

      Jumlah 0 tidak butuh koin. Untuk setiap jumlah yang lebih besar, coba setiap koin yang tidak lebih besar darinya: sisa setelah koin itu adalah jumlah yang lebih kecil dan sudah ada di tabel, jadi satu koin lagi memberi satu kandidat. Kandidat terkecil masuk ke sel, dan koin yang menghasilkannya disimpan di baris di bawahnya. Setelah tabel penuh, koin-koin dibaca mundur dari target: ambil koin terakhirnya, pindah ke jumlah yang tersisa, dan ulangi sampai 0.

      Banyaknya cara

      Untuk menghitung kombinasi, bukan urutan, tabel menambahkan satu koin per baris. Sebuah sel menghitung cara membentuk jumlahnya dengan koin-koin sampai barisnya: cara tanpa koin terbaru, yaitu sel di atas, ditambah cara yang memakai koin terbaru setidaknya sekali, yaitu sel sejauh nilai koin itu ke kiri pada baris yang sama. Karena koin ditambahkan dalam urutan tetap, 1 + 2 dan 2 + 1 adalah cara yang sama dan dihitung sekali.

      Pertanyaan yang sering diajukan

      Mengapa metode greedy gagal?

      Greedy selalu mengambil koin terbesar yang muat dan tidak pernah mempertimbangkan ulang. Dengan koin 1, 3, dan 4 serta jumlah 6, ia mengambil 4, lalu 1 dan 1: tiga koin, padahal dua koin 3 sudah cukup. Untuk sistem koin seperti euro atau dolar AS, greedy kebetulan optimal; sistem seperti itu disebut kanonik.

      Apa bedanya menghitung cara dan menghitung urutan?

      Cara menganggap 1 + 2 dan 2 + 1 sebagai kombinasi yang sama; urutan menghitungnya terpisah. Aplikasi ini menghitung cara dengan menambahkan koin satu baris demi satu baris. Untuk menghitung urutan, telusuri jumlah-jumlahnya dan coba setiap koin untuk masing-masing jumlah.

      Seberapa cepat algoritma penukaran koin?

      Kedua tabel butuh langkah sebanyak banyaknya jenis koin dikali nilai jumlahnya. Itu cepat untuk jumlah dalam ribuan, tetapi jumlah bisa berupa bilangan yang sangat besar, jadi jika diukur dari banyaknya digit, masalah ini secara umum NP-hard.

      Bagaimana jika suatu jumlah tidak bisa dibentuk?

      Selnya tetap ∞, misalnya jumlah 1 dan 3 dengan koin 2 dan 5. Dalam mode Banyaknya cara, hitungannya cukup 0.

      Apakah ada data yang dikirim ke suatu tempat?

      Tidak. Semuanya dihitung di browser Anda, dan pengaturan terakhir Anda tetap tersimpan di penyimpanan lokal browser ini.

      Siap mencobanya?

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

      Ke Editor