My first Magazine pemrograman-kompetitif-dasar | Page 82

7 Dynamic Programming
Algoritma 33 Knapsack secara bottom-up dengan optimisasi flying table lebih jauh.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
function SOLVE ()
d p ← new integer[G + 1]
for c ← 0, G do
d p[c] ← 0
end for
for i ← 1, N do
for c ← G down to w[i] do
d p[c] ← max(d p[c], d p[c − w[i]] + v[i])
end for
end for
return d p[G]
end function
7.2.2 Coin Change
Coin Change merupakan salah satu persoalan DP klasik. Persoalan DP Coin Change
memiliki 2 variasi. Variasi pertama adalah dengan jumlah koin tak hingga. Kita sudah mempelajari
variasi ini serta cara penyelesaiannya di subbab sebelumnya. Variasi kedua adalah jika tiap koin
hanya berjumlah satu buah, seperti yang tertera pada deskripsi soal berikut.
Contoh Soal 7.3: Coin Change
Diberikan M jenis koin, masing-masing jenis bernilai a 1 , a 2 , ..., a M rupiah. Asumsikan banyak-
nya koin untuk setiap nominal adalah satu buah. Tentukan banyaknya koin paling sedikit
untuk membayar tepat sebesar N rupiah!
Contoh
Diberikan koin-koin [1, 1, 1, 5, 5, 5, 7]. Jika kita ingin menukar 15 rupiah, solusinya adalah
dengan menggunakan tiga keping 5. Namun jika kita ingin menukar 20 rupiah, maka solusinya
adalah dengan menggunakan koin-koin 1, 1, 1, 5, 5 dan 7.
Kita tidak dapat menerapkan solusi dengan asumsi jumlah koin tak berhingga yang sudah
dijelaskan di subbab sebelumnya. Pada kasus ini, kita dapat menerapkan intuisi yang serupa
dengan persoalan Knapsack . Definisikan fungsi d p(i, c) sebagai koin minimum yang diperlukan
untuk menukar c rupiah, jika kita hanya mempunyai koin ke-1 sampai ke-i. Jika c = 0, artinya kita
ingin menukar 0 rupiah, sehingga jumlah koin minimum adalah 0. Sementara jika i = 0 dan c > 0,
artinya tidak ada koin yang tersedia untuk menukar c, sehingga d p(0, c) = ∞.
Selain base case tersebut, kita memiliki paling banyak dua pilihan, mengambil koin ke-i, atau
tidak mengambil koin ke-i. Jika kita mengambil koin ke-i, maka kita mendapatkan subpersoalan
d p(i − 1, c − a i ), sementara jika kita tidak mengambil koin ke-i, kita mendapatkan subpersoalan
d p(i − 1, c). Dari kedua kemungkinan tersebut, pilih yang memberikan nilai terkecil. Dengan
demikian, d p(i, c) dapat dirumuskan sebagai berikut:

0,
c = 0



∞,
c > 0 ∧ i = 0
d p(i, c) =
d
p(i
−
1,
c),
i
> 0 ∧ c < a i



min(d p(i − 1, c − a i ) + 1, d p(i − 1, c)), i > 0 ∧ c ≥ a i
72