KAL
Menu

DP dua dimensi

Lintasan kisi, knapsack, dan longest common subsequence dengan tabel dua dimensi.

Daftar isi

DP dua dimensi adalah pola pemrograman dinamis yang selnya diindeks dua angka, biasanya dp[i][j] yang merangkum jawaban untuk sepasang prefiks masukan. Dimensi kedua muncul begitu keputusan dipengaruhi dua hal sekaligus, misalnya posisi di kisi, atau nomor barang dan sisa kapasitas ransel. Topik ini mengerjakan tiga soal andalannya, yaitu lintasan kisi, knapsack 0/1, dan longest common subsequence, dengan tabel dua dimensi yang dicetak penuh pada keluaran agar isi tabelnya terbaca.

Lintasan kisi#

Soal lintasan kisi menghitung banyak lintasan dari pojok kiri atas ke kanan bawah sebuah kisi, bila gerakan hanya boleh ke kanan atau ke bawah. Sel dp[i][j] menyimpan banyak lintasan menuju sel itu, dan langkah terakhir setiap lintasan pasti tiba dari atas atau dari kiri. Kedua kumpulan asal itu tidak beririsan, sehingga keduanya tinggal dijumlahkan:

dp[i][j]=dp[i−1][j]+dp[i][j−1],dp[0][j]=dp[i][0]=1 dp[i][j] = dp[i-1][j] + dp[i][j-1], \qquad dp[0][j] = dp[i][0] = 1

Tepi tabelnya berisi satu, karena hanya ada satu cara melaju lurus di baris pertama maupun kolom pertama. Wilayah dalam tabel baru diisi mulai indeks 1, karena tepinya sudah dijaga basis tersebut. Dengan begitu seluruh isi tabel sah tanpa percabangan khusus di dalam perulangan utamanya.

python lintasan-kisi.py 
"""Lintasan kisi: banyak lintasan dari pojok kiri atas ke kanan bawah."""

baris, kolom = 3, 4

def lintasan(m, n):
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        dp[i][0] = 1           # kolom pertama: hanya satu cara, lurus ke bawah
    for j in range(n):
        dp[0][j] = 1           # baris pertama: hanya satu cara, lurus ke kanan
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp

dp = lintasan(baris, kolom)
for i in range(baris):
    print(f"baris {i}: {dp[i]}")
print(f"banyak lintasan {baris}x{kolom}: {dp[baris - 1][kolom - 1]}")
text Keluaran 
baris 0: [1, 1, 1, 1]
baris 1: [1, 2, 3, 4]
baris 2: [1, 3, 6, 10]
banyak lintasan 3x4: 10
baris demi baris01230121111123413610dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
Tabel dp kisi 3x4 dengan arah pengisian baris demi baris dan sel yang dihitung dari atas dan kiri

Diagram menyorot sel dp[1][2] = 3 yang lahir dari dp[0][2] = 1 di atasnya dan dp[1][1] = 2 di kirinya. Pengisiannya berjalan baris demi baris dari kiri ke kanan, sehingga setiap sel yang dirujuk pasti sudah terisi. Keluaran menunjukkan angka pojok kanan bawah bernilai 10, yang berarti sepuluh lintasan berbeda menghubungkan dua pojok kisi 3x4.

Knapsack 0/1#

Soal knapsack 0/1 menyediakan barang dengan beban dan nilai, lalu menanyakan nilai maksimum yang muat dalam kapasitas tertentu, dengan tiap barang hanya boleh diambil sekali. Sel dp[i][c] menyimpan nilai maksimum memakai i barang pertama dengan kapasitas c. Barang ke-i punya dua nasib, yaitu dilewati sehingga jawabannya dp[i-1][c], atau diambil sehingga jawabannya nilai barang itu ditambah dp[i-1][c - w_i], dengan syarat bebannya muat. Baris pertama dan kolom pertama tabelnya nol, karena nol barang maupun nol kapasitas menghasilkan nol nilai, dan basis itulah yang membuat rumus berlaku mulai kolom 0:

dp[i][c]=max⁡(dp[i−1][c], dp[i−1][c−wi]+vi) dp[i][c] = \max\bigl(dp[i-1][c],\ dp[i-1][c - w_i] + v_i\bigr)
python knapsack-ransel.py 
"""Knapsack 0/1: nilai maksimum peralatan yang muat dalam kapasitas ransel."""

barang = [            # (nama, beban kg, nilai)
    ("matras", 1, 1),
    ("tenda", 3, 4),
    ("kompor", 4, 5),
    ("tungku", 5, 7),
]
kapasitas = 7

def knapsack(barang, kapasitas):
    dp = [[0] * (kapasitas + 1) for _ in range(len(barang) + 1)]
    for i in range(1, len(barang) + 1):
        beban, nilai = barang[i - 1][1], barang[i - 1][2]
        for c in range(kapasitas + 1):
            dp[i][c] = dp[i - 1][c]                 # barang i tidak diambil
            if beban <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - beban] + nilai)
    return dp

dp = knapsack(barang, kapasitas)
label = ["i=0 kosong"] + [f"i={i + 1} {barang[i][0]}" for i in range(len(barang))]
print("kapasitas c :", " ".join(f"{c:2d}" for c in range(kapasitas + 1)))
for i in range(len(barang) + 1):
    print(f"{label[i]:12s}:", " ".join(f"{v:2d}" for v in dp[i]))
print("nilai maksimum:", dp[len(barang)][kapasitas])
text Keluaran 
kapasitas c :  0  1  2  3  4  5  6  7
i=0 kosong  :  0  0  0  0  0  0  0  0
i=1 matras  :  0  1  1  1  1  1  1  1
i=2 tenda   :  0  1  1  4  5  5  5  5
i=3 kompor  :  0  1  1  4  5  6  6  9
i=4 tungku  :  0  1  1  4  5  7  8  9
nilai maksimum: 9

Tabelnya memuat mekanisme lengkapnya. Baris kompor menunjukkan lonjakan di kolom 7 dari 5 menjadi 9, yaitu tenda dan kompor (beban 3 + 4) mengalahkan tungku yang bebannya pas 7 tetapi nilainya hanya 7. Kolom 5 dan 6 justru memilih tungku dengan nilai 7 dan 8, karena tenda dan kompor belum muat di sana. Satu tabel, dua keputusan berbeda per kapasitas, inilah yang tidak bisa ditangkap oleh pilihan serakah mana pun.

Longest common subsequence#

Longest common subsequence (LCS) mencari huruf-huruf yang sama dari dua string, diambil berurutan tetapi boleh melompati huruf di antaranya. Sel dp[i][j] menyimpan panjang LCS antara prefiks s1 sepanjang i dan prefiks s2 sepanjang j. Bila karakter terakhir kedua prefiks sama, keduanya dipasangkan dan jawabannya lahir dari diagonal, sedangkan bila berbeda, salah satu karakternya dibuang dan maksimum dua kandidat itu dimenangkan. Rumus berikut memakai penomoran karakter mulai dari 1:

dp[i][j]={dp[i−1][j−1]+1,s1[i]=s2[j]max⁡(dp[i−1][j], dp[i][j−1]),selainnya dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & s_1[i] = s_2[j] \\ \max(dp[i-1][j],\ dp[i][j-1]), & \text{selainnya} \end{cases}
python lcs-tabel.py 
"""Longest common subsequence dengan tabel dua dimensi."""

s1, s2 = "dinamis", "dinasti"

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

def susun_lcs(s1, s2, dp):
    i, j = len(s1), len(s2)
    huruf = []
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            huruf.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(huruf))

dp = lcs(s1, s2)
print("s1:", s1)
print("s2:", s2)
for row in dp:
    print(row)
print("panjang LCS:", dp[len(s1)][len(s2)], "| LCS:", susun_lcs(s1, s2, dp))
text Keluaran 
s1: dinamis
s2: dinasti
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 2, 2, 2, 2, 2, 2]
[0, 1, 2, 3, 3, 3, 3, 3]
[0, 1, 2, 3, 4, 4, 4, 4]
[0, 1, 2, 3, 4, 4, 4, 4]
[0, 1, 2, 3, 4, 4, 4, 5]
[0, 1, 2, 3, 4, 5, 5, 5]
panjang LCS: 5 | LCS: dinai

Tabel 8x8 itu terbaca seperti peta. Lonjakan diagonal terjadi pada huruf d, i, n, dan a yang dimiliki kedua string, sedangkan huruf m di s1 tidak menemukan pasangannya sehingga barisnya berhenti di 4. Lompatan terakhir muncul di kolom paling kanan, saat huruf i terakhir pada s2 dipasangkan dengan huruf i pada s1. Hasilnya dinai sepanjang 5, dan fungsi susun_lcs menelusuri tabel mundur untuk merekonstruksinya.

Varian Java#

Ketiga soal kembali diterjemahkan ke Java dalam satu berkas. Array dua dimensi Java dan Python berperilaku sama untuk tabel yang ukurannya sudah pasti, sehingga tiga rumus transisinya nyaris disalin apa adanya.

java DpDuaDimensi.java 
public class DpDuaDimensi {
    // tiga soal DP dua dimensi: lintasan kisi, knapsack 0/1, dan LCS

    static int lintasan(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    static int knapsack(int[][] barang, int kapasitas) {
        int[][] dp = new int[barang.length + 1][kapasitas + 1];
        for (int i = 1; i <= barang.length; i++) {
            int beban = barang[i - 1][0], nilai = barang[i - 1][1];
            for (int c = 0; c <= kapasitas; c++) {
                dp[i][c] = dp[i - 1][c];
                if (beban <= c) {
                    dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - beban] + nilai);
                }
            }
        }
        return dp[barang.length][kapasitas];
    }

    static int lcs(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        int[][] barang = {{1, 1}, {3, 4}, {4, 5}, {5, 7}};
        System.out.println("lintasan 3x4       : " + lintasan(3, 4));
        System.out.println("knapsack c=7       : " + knapsack(barang, 7));
        System.out.println("LCS dinamis-dinasti: " + lcs("dinamis", "dinasti"));
    }
}
text Keluaran 
lintasan 3x4       : 10
knapsack c=7       : 9
LCS dinamis-dinasti: 5

Tiga angkanya sama dengan versi Python, yaitu 10 lintasan, nilai knapsack 9, dan LCS sepanjang 5. Perbedaan bahasanya kecil, seperti s1.charAt(i - 1) menggantikan s1[i - 1], sedangkan bentuk tabel (m + 1) x (n + 1) dan arah pengisiannya tetap persis sama. Pengisian pada ketiga fungsi bergerak baris demi baris dari kiri ke kanan, sehingga sel diagonal, atas, dan kiri selalu selesai lebih dulu. Berbeda dari Python yang membangun list per baris, new int[m][n] di Java sudah mengisi seluruh tabel dengan nol, sehingga baris dan kolom basis LCS serta knapsack tidak perlu diisi manual. Keluaran tiga barisnya ringkas karena tabel penuhnya sudah dipajang pada versi Python, dan kodenya dijalankan sebagai satu berkas dengan perintah java DpDuaDimensi.java.

Kesalahan umum#

  1. Memangkas tabel menjadi m x n. Baris dan kolom tambahan itu menyimpan prefiks kosong yang menjadi basis. Tanpa keduanya, indeks negatif atau percabangan khusus bermunculan, dan biasanya tetap salah di pojok.
  2. Membaca baris yang sama pada knapsack 0/1. Kekeliruan ini tidak memunculkan error, jawabannya hanya membengkak karena barang diambil berulang. Kandidat pengambilan selalu membaca dp[i-1].
  3. Mengisi LCS dengan urutan yang membaca sel yang belum terisi. Loop i luar dan j dalam aman karena sel diagonal, atas, dan kiri sudah pasti selesai. Mengubah arah tanpa memeriksa ketergantungan membuat tabel terisi dengan angka yang belum jadi.
  4. Mencampur LCS dengan substring. LCS boleh melompati huruf, sedangkan longest common substring menuntut hurufnya berurutan. Pada dinamis dan dinasti, jawaban LCS adalah dinai dengan lonjakan terakhir yang terpisah jauh dari lonjakan sebelumnya, sedangkan jawaban substring hanyalah dina karena hurufnya harus berurutan tanpa celah. Menjalankan rumus yang salah memberi angka yang tampak masuk akal tetapi menjawab soal yang lain.

Ringkasan#

  • Sel dp[i][j] merangkum jawaban sepasang prefiks, dengan basis di baris dan kolom pertama.
  • Lintasan kisi menjumlahkan sel atas dan sel kiri, menghasilkan 10 lintasan untuk kisi 3x4.
  • Knapsack 0/1 membandingkan barang yang dilewati dengan barang yang diambil, membaca selalu baris dp[i-1], dan berakhir di 9 untuk kapasitas 7.
  • LCS memakai diagonal bila karakter sama dan maksimum atas-kiri bila berbeda, menghasilkan dinai sepanjang 5 untuk dinamis dan dinasti.

Referensi#