Ide: Menghitung Koin dengan Menimbang

Dua atau tiga minggu yang lalu saya menyetorkan uang di celengan ke Bank. Seperti biasanya, saya harus mengelompokkan koin satu per satu. Setiap sepuluh koin bernominal sama, diselotip hingga membentuk nominal yang sepuluh kali lebih besar. Sesampainya di bank, teller menghitung uang receh saya satu per satu, tanpa bantuan mesin.

Koin

Mengapa Bank di Indonesia tidak punya mesin penghitung koin? Mesin penghitung uang kertas biasanya sudah ada, tapi koin? Sama sekali tidak ada. Saya bahkan pernah dimarahi teller ketika setor dan koin belum dikelompokkan.

Saya jadi kepikiran, bagaimana caranya menghitung koin dengan mudah? Karena ini menyangkut uang, jadi harus akurat. Salah satu yang ada di pikiran saya adalah menimbangnya! Uang koin punya berat (well, massa kalau Anda seorang fisikawan sejati) yang berbeda-beda.

Berdasarkan wikipedia, uang koin yang umum beredar saat ini adalah:

  • 50 rupiah putih: 1.36 gram,
  • 100 rupiah putih: 1.79 gram,
  • 200 rupiah putih: 2.38 gram,
  • 500 rupiah kuning 1991: 5.29 gram,
  • 500 rupiah kuning 1997: 5.34 gram,
  • 500 rupiah putih: 3.10 gram,
  • 1000 rupiah putih-kuning: 8.60 gram,
  • 1000 rupiah putih: 4.50 gram

Katakanlah saya punya timbangan yang ketelitiannya 10 mg (mungkin biasa dipakai apoteker atau tukang emas). Dengan menimbang koin yang saya miliki, bisakah saya menentukan jumlah uang yang saya punya?

Misalkan a, b, c, d, e, f, g, dan adalah jumlah dari setiap jenis koin di atas, dan w adalah total berat dari koin di atas. Maka seharusnya persamaan ini bisa dipenuhi:

1.36a + 1.79b + 2.38c + 5.29d + 5.34e + 3.10f + 8.60g + 4.50h = w

Misalkan saya punya 100 koin seribuan putih, 80 koin limaratusan putih, dan 250 koin duaratusan, total uang yang saya punya adalah 190 000 rupiah dan beratnya 1293 gram. Persamaan di atas menjadi:

1.36a + 1.79b + 2.38c + 5.29d + 5.34e + 3.10f + 8.60g + 4.50h = 1293

Saya butuh bantuan matematikawan di sini:

  • Apakah persamaan tersebut dapat diselesaikan, sehingga diperoleh (a, b, c, d, e, f, g, h) = (0, 0, 250, 0, 0, 80, 0, 100)? Tidak masalah bila memerlukan data tambahan yang disimpan, bisa diatur.
  • Apabila dapat diselesaikan, apakah solusi tersebut unik? Karena bila tidak unik, tentu saja kita perlu mengatur strategi agar uang yang terhitung akurat.

Beberapa kemungkinan metode yang sudah saya baca-baca, dan mungkin bisa diterapkan:

Persamaan Diophantine

Persamaan di atas jelas memerlukan solusi a, b, c, d, e, f, g, dan h integer non-negatif, karena koin tidak mungkin pecahan bukan? Bukankah ini definisi dari persamaan diophantine?

Tapi saya tak banyak mengerti tentang teori bilangan, di Wikipedia pun hanya tersedia untuk 2 variabel, apakah untuk 8 variabel akan tetap sama? Well, need help here.

Apakah ada hubungannya dengan GCD dan LCM dari tiap-tiap berat koin?

Brute Force

Engineering solution starts here. Kita coba satu per satu nilai a, b, c, d, e, f, g, dan h. Untuk setiap variabel, kita coba sampai beratnya mencapai total berat koin.

Intinya nested for sampai 8 kali ke dalam. Tentu saja tidak efisien karena kompleksitasnya O(n^8), tapi sepertinya cara ini paling mudah dilakukan, sekaligus tahu apakah solusi tersebut unik atau tidak.

Aljabar Linier

Persamaan di atas terdiri dari 8 variabel, bisakah kita menyelesaikannya kalau kita punya 8 persamaan? Tujuh (atau lebih) persamaan yang lain kita simpan sebagai referensi dalam program.

Tapi sepertinya cara ini tidak bisa diterapkan, saya masih bingung memikirkan bagaimana caranya menyimpan referensinya.

Lainnya

Saya membaca referensi di reddit (internet positif, crap) namun lupa linknya. Beberapa user mengusulkan menggunakan weight to value ratio, ada pula yang mengatakan ini berhubungan dengan Knapsack Problem.

Bisakah ide ini dieksekusi? Entahlah.

5 thoughts on “Ide: Menghitung Koin dengan Menimbang

  1. apakah gcd tiap 2, 3, …, 8 koin semuanya 1, atau ada yang tidak 1? kalau memang cuma 1, solusi unik semakin besar peluangnya (meskipun mungkin saja ada yang tidak unik).

    mengenai diophantine, bisa untuk lebih dari 2 variabel kok :3 gabungannya sama crt ntar

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s