-
Bayu memiliki koin uang 200, 300, 500, dan 700 yang sangat banyak. Ia berniat untuk membeli buku pemrograman seharga 2000. Karena koin uang tersebut cukup berat apabila ditaruh dalam kantung celana, ia hanya ingin membawa uang seminimal mungkin. Untuk itu, koin yang seharusnya ia bawa sebanyak … keping. {tuliskan dalam bentuk angka}
Asumsikan bahwa ia ingin membawa uang pas.
Jika ia butuh 200,300,500 atau 700 lagi, ia hanya perlu memilih 1 uang lagi.
Misalkan f(x) adalah uang minimum yang ia butuhkan untuk mendapatkan koin senilai x.
f(400) = 2 (200 + 200)
f(600) = 2 (300 + 300)
f(800) = 2 (500 + 300)
f(900) = 2 (700 + 200)
f(1000) = 2 (700 + 300)
f(1100) = 3 (200 + f(900))
f(1200) = 2 (700 + 500)
f(1300) = min(f(1100) + 1, f(1000) + 1, f(800) + 1, f(600) + 1) = min(4,3,3,3) = 3
f(1400) = min(f(1200) + 1, f(1100) + 1, f(900) + 1, f(700) + 1) = min(3,4,3,2) = 2
f(1500) = min(f(1300) + 1, f(1200) + 1, f(1000) + 1, f(800) + 1) = min(4,3,3,3) = 3
f(1600) = min(f(1400) + 1, f(1300) + 1, f(1100) + 1, f(900) + 1) = min(3,4,4,3) = 3
f(1700) = min(f(1500) + 1, f(1400) + 1, f(1200) + 1, f(1000) + 1) = min(4,3,3,3) = 3
f(1800) = min(f(1600) + 1, f(1500) + 1, f(1300) + 1, f(1100) + 1) = min(4,4,4,4) = 4
f(1900) = min(f(1700) + 1, f(1600) + 1, f(1400) + 1, f(1200) + 1) = min(4,4,3,3) = 3
f(2000) = min(f(1800) + 1, f(1700) + 1, f(1500) + 1, f(1300) + 1) = min(5,4,4,4) = 4
Dengan demikian ia membawa 4 keping uang.
