Belajar Algoritm - DP Klasik: Knapsack, LCS & Edit Distance
Tiga masalah DP fundamental: 0/1 Knapsack dengan space optimization 1D, Longest Common Subsequence dengan trace-back path, dan Edit Distance (Levenshtein) dengan operasi insert/delete/replace.
#Pendahuluan
Setelah di episode 14 kita memahami fondasi Dynamic Programming — memoization vs tabulation dan pola 1D state — pada episode ini kita membahas tiga masalah DP paling klasik: 0/1 Knapsack, Longest Common Subsequence (LCS), dan Edit Distance. Ketiganya menggunakan 2D state (dua variabel), yang merupakan lompatan kompleksitas dari pola 1D di episode sebelumnya.
Ketiga masalah ini bukan hanya teori — mereka muncul langsung di production: Knapsack untuk resource allocation, LCS untuk diff tools dan version control, Edit Distance untuk spell checker dan DNA sequence alignment.
#0/1 Knapsack
0/1 Knapsack: diberikan item dengan weight dan value, pilih item sehingga total weight ≤ capacity dan total value maksimum. Setiap item hanya bisa diambil sekali (0 atau 1).
#2D State
def knapsack_2d(weights, values, capacity):
n = len(weights)
# dp[i][w] = max value dari item 0..i dengan capacity w
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# Tidak ambil item i
dp[i][w] = dp[i - 1][w]
# Ambil item i (jika muat)
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i - 1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]#Space Optimization 1D
Karena dp[i][w] hanya bergantung pada dp[i-1][...], kita bisa optimasi ke 1D array:
def knapsack_1d(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
# Iterasi w dari capacity ke weights[i] (backward!)
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]Mengapa backward? Jika forward, item yang sama bisa diambil lebih dari sekali (menjadi unbounded knapsack). Backward memastikan setiap item hanya dipertimbangkan sekali.
Note
0/1 Knapsack space optimization dari O(n × capacity) ke O(capacity) adalah contoh klasik bagaimana memahami dependency pattern DP bisa menghemat memori secara dramatis. Ini sering diminta di interview sebagai follow-up.
#Subset Sum Variation
Subset sum: apakah ada subset yang jumlahnya persis target? Ini adalah spesialisasi 0/1 Knapsack (value = weight, cari yang = capacity).
def subset_sum(nums, target):
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for w in range(target, num - 1, -1):
dp[w] = dp[w] or dp[w - num]
return dp[target]#Longest Common Subsequence (LCS)
LCS: cari subsequence terpanjang yang umum dari dua string. Subsequence berarti karakter tidak harus berurutan tetapi urutannya dipertahankan.
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]#Trace-back Path
Untuk menemukan subsequence aktual (bukan hanya panjangnya), trace-back dari dp[m][n]:
def lcs_string(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Trace-back
result = []
i, j = m, n
while i > 0 and j > 0:
if s1[i-1] == s2[j-1]:
result.append(s1[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))LCS adalah dasar dari diff tools (git diff, diffutils) — diff menampilkan LCS sebagai garis yang tidak berubah, dan sisanya sebagai tambahan/hapus.
#Edit Distance (Levenshtein)
Edit Distance: jumlah operasi minimum (insert, delete, replace) untuk mengubah string A menjadi string B.
def edit_distance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i # hapus semua karakter
for j in range(n + 1):
dp[0][j] = j # insert semua karakter
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] # cocok, tidak perlu operasi
else:
dp[i][j] = 1 + min(
dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1] # replace
)
return dp[m][n]#Tampilkan Operasi
Modifikasi untuk menampilkan operasi yang dilakukan:
def edit_distance_ops(s1, s2):
# ... (dp computation sama) ...
# Trace-back
ops = []
i, j = m, n
while i > 0 or j > 0:
if i > 0 and j > 0 and s1[i-1] == s2[j-1]:
ops.append(f"Keep '{s1[i-1]}'")
i -= 1; j -= 1
elif i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + 1:
ops.append(f"Replace '{s1[i-1]}' with '{s2[j-1]}'")
i -= 1; j -= 1
elif i > 0 and dp[i][j] == dp[i-1][j] + 1:
ops.append(f"Delete '{s1[i-1]}'")
i -= 1
else:
ops.append(f"Insert '{s2[j-1]}'")
j -= 1
return list(reversed(ops))Tip
Edit distance digunakan di spell checker (kata terdekat dengan edit distance minimum), DNA alignment (biologi molekuler), dan fuzzy search. Library seperti Python's fuzzywuzzy dan Elasticsearch's fuzzy query menggunakan edit distance di balik layar.
#Kompleksitas Ketiga Masalah
| Masalah | State | Time | Space |
|---|---|---|---|
| 0/1 Knapsack | dp[i][w] | O(n × W) | O(W) — optimized |
| LCS | dp[i][j] | O(m × n) | O(m × n) |
| Edit Distance | dp[i][j] | O(m × n) | O(m × n) |
#Penutup
Pada episode 15 ini, kalian telah memahami:
- 0/1 Knapsack: 2D state → space optimization 1D dengan backward iteration.
- LCS: dp[i][j] = LCS dari s1[0..i-1] dan s2[0..j-1]; trace-back untuk subsequence.
- Edit Distance: dp[i][j] = operasi minimum; min insert/delete/replace.
- Ketiganya menggunakan 2D state dengan O(m × n) time.
Di episode 16 selanjutnya kita akan membahas DP on Strings — masalah string yang lebih kompleks: longest palindromic subsequence, word break, dan wildcard matching. Sampai jumpa di episode 16!