Rangkuman: Subset Sum Problem

Dynamic Programming / Backtracking

1. Pengertian

Subset Sum Problem adalah masalah penentuan apakah ada subset dari sekumpulan bilangan bulat positif yang jumlahnya sama dengan target tertentu. Ini adalah masalah NP-Complete dalam kasus umum, tetapi dapat diselesaikan secara efisien dengan algoritma pseudo-polinomial menggunakan **Dynamic Programming** atau dengan **Backtracking**.

Contoh: Diberikan set $S = \{3, 34, 4, 12, 5, 2\}$ dan target sum $T = 9$. Apakah ada subset dari $S$ yang jumlahnya 9? Ya, $\{4, 5\}$ atau $\{3, 4, 2\}$.

2. Konsep Dasar & Pendekatan

Ada dua pendekatan umum untuk menyelesaikan Subset Sum Problem:

a. Pendekatan Dynamic Programming (DP)

Pendekatan DP melibatkan pembuatan tabel (biasanya boolean) yang menunjukkan apakah suatu jumlah dapat dicapai dengan menggunakan subset dari item-item yang telah dipertimbangkan hingga saat ini.

Langkah-langkah DP:

  1. Buat tabel boolean `dp[sum+1][n+1]`, di mana `dp[i][j]` bernilai `true` jika jumlah `i` dapat dibentuk menggunakan subset dari `j` item pertama.
  2. Inisialisasi `dp[0][j]` sebagai `true` (jumlah 0 selalu dapat dibentuk dengan subset kosong) dan `dp[i][0]` sebagai `false` (kecuali `dp[0][0]`) untuk `i > 0`.
  3. Isi tabel secara iteratif:
    • Untuk setiap item `arr[j-1]` dan setiap jumlah `i`:
    • `dp[i][j] = dp[i][j-1]` (tidak menyertakan item saat ini)
    • Jika `i >= arr[j-1]`, maka `dp[i][j] = dp[i][j] OR dp[i - arr[j-1]][j-1]` (menyertakan item saat ini).
  4. Hasilnya ada di `dp[target_sum][n]`.

b. Pendekatan Backtracking

Pendekatan backtracking mengeksplorasi semua kemungkinan subset secara rekursif. Pada setiap langkah, untuk setiap elemen, ada dua pilihan: menyertakannya dalam subset atau tidak.

Langkah-langkah Backtracking:

  1. Mulai dengan jumlah saat ini 0 dan indeks item pertama.
  2. Pada setiap langkah rekursif, ada dua cabang:
    • Sertakan item saat ini: Tambahkan item ke jumlah saat ini dan rekursif panggil untuk item berikutnya.
    • Jangan sertakan item saat ini: Rekursif panggil untuk item berikutnya tanpa menambahkan item saat ini ke jumlah.
  3. Jika jumlah saat ini sama dengan target, solusi ditemukan.
  4. Jika jumlah saat ini melebihi target atau semua item sudah dipertimbangkan tanpa mencapai target, backtrack.

3. Contoh Ilustrasi (DP)

Set $S = \{2, 3, 7, 8, 10\}$, Target Sum $T = 11$.

Tabel DP (kolom mewakili item, baris mewakili sum):


Sum\Item | {} | {2} | {2,3} | {2,3,7} | {2,3,7,8} | {2,3,7,8,10}
------------------------------------------------------------------
0        | T  | T   | T     | T       | T         | T
1        | F  | F   | F     | F       | F         | F
2        | F  | T   | T     | T       | T         | T
3        | F  | F   | T     | T       | T         | T
4        | F  | T   | T     | T       | T         | T
5        | F  | F   | T     | T       | T         | T
6        | F  | T   | T     | T       | T         | T
7        | F  | F   | F     | T       | T         | T
8        | F  | T   | F     | T       | T         | T
9        | F  | F   | T     | T       | T         | T
10       | F  | T   | F     | T       | T         | T
11       | F  | F   | T     | T       | T         | T  (True, ada subsetnya)

4. Pseudocode Algoritma (DP)


FUNCTION isSubsetSum(set, n, sum):
    // dp[i][j] is true if sum 'i' can be achieved with elements from set[0...j-1]
    dp = CREATE BOOLEAN ARRAY of size (sum + 1) x (n + 1)

    // Jika sum adalah 0, maka hasilnya true (dengan subset kosong)
    FOR j FROM 0 TO n:
        dp[0][j] = TRUE

    // Jika set kosong dan sum > 0, maka hasilnya false
    FOR i FROM 1 TO sum:
        dp[i][0] = FALSE

    // Isi tabel dp secara bottom up
    FOR i FROM 1 TO sum: // Iterasi untuk setiap kemungkinan jumlah
        FOR j FROM 1 TO n: // Iterasi untuk setiap item di set
            dp[i][j] = dp[i][j-1] // Case 1: Tidak menyertakan item set[j-1]

            IF i >= set[j-1]:
                dp[i][j] = dp[i][j] OR dp[i - set[j-1]][j-1] // Case 2: Menyertakan item set[j-1]

    RETURN dp[sum][n] // Hasil akhir

5. Kompleksitas Waktu & Ruang

  • Kompleksitas Waktu (DP): $O(sum \times N)$, di mana $N$ adalah jumlah elemen dalam set, dan $sum$ adalah target jumlah. Ini adalah pseudo-polinomial karena tergantung pada nilai `sum`, bukan hanya ukuran input.
  • Kompleksitas Waktu (Backtracking): $O(2^N)$ pada kasus terburuk, karena setiap elemen memiliki dua kemungkinan (disertakan atau tidak).
  • Kompleksitas Ruang (DP): $O(sum \times N)$ untuk tabel DP. Bisa dioptimalkan menjadi $O(sum)$ jika hanya menyimpan dua baris terakhir.
  • Kompleksitas Ruang (Backtracking): $O(N)$ untuk stack rekursi.

6. Aplikasi

  • क्रिप्टografi (subset sum adalah masalah yang sulit).
  • Pengoptimalan sumber daya (misalnya, memilih item untuk dipaketkan ke dalam kapasitas tertentu).
  • Pembuatan sistem kasir untuk memberikan kembalian dengan koin/uang kertas yang tersedia.
  • Manajemen inventaris.
Kembali ke Materi Materi Selanjutnya