Olimpiade Sains Provinsi (OSP) 2016 - Komputer, Nomor 25
Sebagai pendekar, Pak Dengklek dan Pak Ganesh tidak boleh sakit. Supaya sehat, keduanya harus minum air putih 2 liter per hari. Pak Ganesh memiliki 3 buah gelas : satu berukuran 200 ml, satu berukuran 300 ml, and satunya lagi berukuran 500 ml. Berapa banyak urutan minum Pak Ganesh dengan 3 buah gelas tersebut (tidak perlu dipakai semua) apabila ia ingin minum air putih tepat 2 liter? Urutan minum 200-200-200-200-200-500- 500 dan 500-500-200-200-200-200-200 dianggap berbeda.
3 jawaban
Fariskhi Vidyan10 tahun lalu
3
Sebenarnya nomor 24 dan 25 itu mirip dengan coin change problem yang bisa kita selesaikan dengan pendekatan dynamic programming. Dengan menggunakan pendekatan ini, kita bisa menyelesaikan kasus serupa dengan cepat dan benar asalkan teliti menghitungnya. Terkadang kalau kita harus membagi kasus terlebih dahulu, akan memakan waktu lama dan rawan tidak teliti.
Misal, f(n) = banyak urutan minum Pak Ganesh untuk n*100 ml. Kasus dasarnya f(0) = 1, yaitu tidak meminum apa-apa. Untuk suatu f(n), jika terakhirnya Pak Ganesh meminum dari gelas 200 ml maka banyaknya kemungkinan adalah f(n-2). Jika terakhirnya meminum dari gelas 300 ml banyaknya kemungkinan adalah f(n-3). Jika terakhirnya meminum dari gelas 500 ml banyaknya kemungkinan adalah f(n-5). Maka, f(n) = f(n-2) + f(n-3) + f(n-5). Tentu jika n < 0, maka banyaknya kemungkinan adalah 0.
Untuk mempermudah, kita dapat menghitung nilai f(20) secara bottom up.
| f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) | f(9) | f(10) | f(11) | f(12) | f(13) | f(14) | f(15) | f(16) | f(17) | f(18) | f(19) | f(20) |
| 1 | 0 | 1 | 1 | 1 | 3 | 2 | 5 | 6 | 8 | 14 | 16 | 27 | 36 | 51 | 77 | 103 | 144 | 216 | 309 | 448 |
Didapatlah jawaban untuk soal ini, yaitu f(20) = 448.
Glenda Emanuella Sutanto10 tahun lalu
Masuk untuk menulis jawaban