Teknik Desain · Pelajaran 7 dari 10
DP klasik: knapsack dan LCS
12 menit baca · BelajarCode
Knapsack 0/1
Ada n barang dengan berat dan nilai tertentu, serta tas berkapasitas W. Setiap barang boleh diambil atau tidak (tidak bisa dipecah). Maksimalkan total nilai.
- Keadaan: dp[i][w] = nilai maksimum dengan memakai barang 1 sampai i dan kapasitas w.
- Transisi: dp[i][w] = max(dp[i-1][w], dp[i-1][w - berat_i] + nilai_i), pilihan kedua hanya jika berat_i ≤ w.
1def knapsack(barang, kapasitas):2 n = len(barang)3 dp = [[0] * (kapasitas + 1) for _ in range(n + 1)]4 for i in range(1, n + 1):5 berat, nilai = barang[i - 1]6 for w in range(kapasitas + 1):7 dp[i][w] = dp[i - 1][w]8 if berat <= w:9 dp[i][w] = max(dp[i][w], dp[i - 1][w - berat] + nilai)10 diambil = []11 w = kapasitas12 for i in range(n, 0, -1):13 if dp[i][w] != dp[i - 1][w]:14 diambil.append(i - 1)15 w -= barang[i - 1][0]16 return dp[n][kapasitas], sorted(diambil)1718barang = [(10, 60), (20, 100), (30, 120)]19print(knapsack(barang, 50))20barang2 = [(1, 1), (3, 4), (4, 5), (5, 7)]21print(knapsack(barang2, 7))(220, [1, 2]) (9, [1, 2])
Kompleksitasnya Θ(nW). Karena bergantung pada nilai W, bukan panjang masukannya dalam bit, algoritma ini disebut pseudo-polinomial. Knapsack 0/1 termasuk masalah NP-hard, dibahas di pelajaran terakhir.
Longest common subsequence
Subsequence adalah deretan karakter yang diambil dari sebuah string dengan urutan tetap, tetapi boleh melompat. LCS adalah subsequence terpanjang yang dimiliki dua string. LCS dipakai di alat pembanding berkas (diff) dan bioinformatika.
- Keadaan: dp[i][j] = panjang LCS dari i karakter pertama string a dan j karakter pertama string b.
- Transisi: jika a[i-1] = b[j-1], dp[i][j] = dp[i-1][j-1] + 1. Jika tidak, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
1def lcs(a, b):2 m, n = len(a), len(b)3 dp = [[0] * (n + 1) for _ in range(m + 1)]4 for i in range(1, m + 1):5 for j in range(1, n + 1):6 if a[i - 1] == b[j - 1]:7 dp[i][j] = dp[i - 1][j - 1] + 18 else:9 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])10 hasil = []11 i, j = m, n12 while i > 0 and j > 0:13 if a[i - 1] == b[j - 1]:14 hasil.append(a[i - 1])15 i -= 116 j -= 117 elif dp[i - 1][j] >= dp[i][j - 1]:18 i -= 119 else:20 j -= 121 return dp[m][n], "".join(reversed(hasil))2223print(lcs("ALGORITMA", "LOGARITMA"))24print(lcs("PEMROGRAMAN", "PROGRAM"))(7, 'LGRITMA') (7, 'PROGRAM')
Kompleksitasnya Θ(mn) waktu dan memori. Jika hanya panjangnya yang dibutuhkan, memori bisa dihemat menjadi dua baris tabel.
Cek pemahaman
Kenapa knapsack 0/1 dengan DP Θ(nW) tidak dianggap algoritma polinomial?
Latihan
Jarak edit
Jarak edit (Levenshtein) adalah banyaknya operasi minimum (sisip, hapus, ganti satu karakter) untuk mengubah string a menjadi b. Rumuskan dan implementasikan DP-nya, lalu hitung jarak "kucing" ke "kambing".
Pembahasan
- Keadaan: dp[i][j] = jarak edit dari i karakter pertama a ke j karakter pertama b.
- Kasus dasar: dp[i][0] = i dan dp[0][j] = j.
- Transisi: jika karakter sama, dp[i][j] = dp[i-1][j-1]. Jika berbeda, 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) untuk hapus, sisip, atau ganti.
1def jarak_edit(a, b):2 m, n = len(a), len(b)3 dp = [[0] * (n + 1) for _ in range(m + 1)]4 for i in range(m + 1):5 dp[i][0] = i6 for j in range(n + 1):7 dp[0][j] = j8 for i in range(1, m + 1):9 for j in range(1, n + 1):10 if a[i - 1] == b[j - 1]:11 dp[i][j] = dp[i - 1][j - 1]12 else:13 dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])14 return dp[m][n]1516print(jarak_edit("kucing", "kambing"))17print(jarak_edit("algoritma", "algoritma"))3 0
Salah satu urutan operasinya: ganti u menjadi a, ganti c menjadi m, lalu sisipkan b sebelum "ing". Fitur koreksi ejaan memakai ukuran jarak seperti ini.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.