My first Magazine pemrograman-kompetitif-dasar | Page 80

7 Dynamic Programming
Solusi Top-Down
Kita implementasikan d p(i, c) sebagai fungsi SOLVE (i, c) pada Algoritma 30.
Algoritma 30 Knapsack secara top-down .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
function SOLVE (i, c)
if (i = 0) then
return 0
end if
if computed[i][c] then
return memo[i][c]
end if
best ← SOLVE (i − 1, c)
if (c ≥ w[i]) then
best ← max(best, SOLVE (i − 1, c − w[i]) + v[i])
end if
computed[i][c] ← true
memo[i][c] ← best
return best
end function
Jawaban akhirnya ada pada SOLVE (N, G).
Solusi Bottom-Up
Pengisian tabel DP secara bottom-up dapat dilihat pada Algoritma 31.
Algoritma 31 Knapsack secara bottom-up .
function SOLVE ()
2:
for c ← 0, G do
3:
d p[0][c] ← 0
4:
end for
1:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
. Base case
for i ← 1, N do
. Isi "tabel" dari kasus yang kecil ke besar
for c ← 0, G do
best ← d p[i − 1][c]
if (c ≥ w[i]) then
best ← max(best, d p[i − 1][c − w[i]] + v[i])
end if
d p[i][c] ← best
end for
end for
return d p[N][G]
end function
Optimisasi Memori pada Bottom-Up
Terdapat sifat khusus pada perhitungan DP Knapsack secara bottom-up . Perhatikan
bahwa untuk menghitung nilai d p(i, _), hanya dibutuhkan informasi d p(i − 1, _). Informasi d p(0, _),
70