My first Magazine pemrograman-kompetitif-dasar | Page 81

7.2 Contoh-contoh DP Sederhana
d p(1, _), d p(2, _), ..., d p(i − 2, _) tidak lagi dibutuhkan. Dengan demikian, kita dapat menghemat
memori dengan tidak lagi menyimpan informasi yang sudah tidak dibutuhkan.
Untuk mewujudkannya, kita dapat membuat tabel DP yang hanya berukuran 2 × G. Pada
awalnya, baris ke-0 digunakan untuk menyimpan d p(0, _), dan baris ke-1 untuk d p(1, _). Untuk
perhitungan d p(2, _), kita tidak lagi membutuhkan d p(0, _), sehingga baris menyimpan d p(0, _)
dapat ditimpa untuk menyimpan d p(2, _). Demikian pula untuk d p(3, _), yang dapat menimpa
baris yang menyimpan d p(1, _). Secara umum, d p(x, _) akan disimpan pada baris ke-(x mod 2).
Optimisasi seperti ini disebut dengan flying table atau rolling array, dan ditunjukkan pada
Algoritma 32.
Algoritma 32 Knapsack secara bottom-up dengan optimisasi flying table .
function SOLVE ()
d p ← new integer[2][G + 1]
3:
for c ← 0, G do
4:
d p[0][c] ← 0
5:
end for
1:
2:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
for i ← 1, N do
iNow ← i mod 2
iPrev ← 1 − iNow
. Bernilai 0 atau 1 yang merupakan kebalikan dari iNow
for c ← 0, G do
best ← d p[iPrev][c]
if (c ≥ w[i]) then
best ← max(best, d p[iPrev][c − w[i]] + v[i])
end if
d p[iNow][c] ← best
end for
end for
return d p[N mod 2][G]
end function
Dengan optimisasi ini, kebutuhan memorinya berkurang dari O(NG) menjadi O(G). Perlu
diperhatikan bahwa flying table hanya mengurangi kompleksitas memori. Kompleksitas waktu
untuk perhitungan DP tetaplah sama.
Lebih jauh lagi, kita dapat menghilangkan dimensi i pada DP secara sepenuhnya, sehingga
cukup digunakan tabel 1 dimensi berukuran G. Perhatikan bahwa pengisian d p(i, c) hanya bergan-
tung pada dua nilai, yaitu d p(i − 1, c) dan d p(i − 1, c − w[i]), atau dengan kata lain, nilai yang tepat
berada "di atas" dan "di atas kiri" sel sebuah tabel DP. Observasi ini memungkinkan kita untuk
mengisi suatu d p(i, c) dengan c yang menurun dari G sampai dengan w[i], dan langsung menimpa
sel tabel d p(i − 1, c). Pengisian perlu dilakukan dengan c yang menurun (atau bila dilihat pada
tabel DP, dari kanan ke kiri) supaya nilai yang disimpan pada kolom c − w[i] masih merupakan nilai
d p(i − 1, c − w[i]), bukan d p(i, c − w[i]). Optimisasi lanjutan ini ditunjukkan pada Algoritma 33.
Mengoptimisasi memori DP dari 2 × G menjadi G saja mungkin tidak signifikan. Penjelasan
mengenai teknik flying table lebih lanjut ini hanya bertujuan untuk menunjukkan bahwa terdapat
hal-hal menarik yang dapat dilakukan ketika DP diimplementasikan secara bottom-up .
71