Kembali

Masalah Subset Sum

Masalah klasik dalam ilmu komputer: Menentukan apakah ada subset dari himpunan bilangan yang jumlahnya sama dengan nilai target tertentu

Apa itu Subset Sum Problem?

Subset Sum Problem adalah masalah klasik dalam ilmu komputer yang termasuk dalam kategori masalah NP-Complete. Masalah ini bertujuan untuk menentukan apakah ada subset dari sebuah himpunan bilangan bulat yang jumlahnya sama dengan nilai target tertentu.

Masalah ini pertama kali diformalkan dalam teori kompleksitas komputasi dan sejak itu menjadi:

  • Contoh standar masalah NP-Complete
  • Dasar untuk banyak masalah optimasi lainnya
  • Alat pengajaran untuk dynamic programming
  • Topik penelitian dalam algoritma dan kompleksitas

Karakteristik Subset Sum Problem

Input:

  • Himpunan bilangan bulat (biasanya tidak negatif)
  • Nilai target yang ingin dicapai

Output:

  • True jika ada subset yang memenuhi
  • False jika tidak ada subset yang memenuhi

Cara Kerja Subset Sum

Masalah ini dapat diselesaikan dengan beberapa pendekatan:

  1. Brute Force:
    • Memeriksa semua kemungkinan subset
    • Kompleksitas waktu O(2^n)
  2. Dynamic Programming:
    • Menggunakan tabel untuk menyimpan hasil subproblem
    • Kompleksitas waktu O(n*target)
  3. Backtracking:
    • Mencoba kombinasi secara rekursif dengan pemangkasan
    • Lebih efisien daripada brute force

Pseudocode Subset Sum (Dynamic Programming)

subsetSum(numbers, target):
  n = panjang(numbers)
  buat tabel dp[n+1][target+1]
  
  untuk i dari 0 sampai n:
    dp[i][0] = true
  
  untuk j dari 1 sampai target:
    dp[0][j] = false
  
  untuk i dari 1 sampai n:
    untuk j dari 1 sampai target:
      jika numbers[i-1] <= j:
        dp[i][j] = dp[i-1][j] atau dp[i-1][j-numbers[i-1]]
      lain:
        dp[i][j] = dp[i-1][j]
  
  kembalikan dp[n][target]

Implementasi JavaScript

function subsetSum(numbers, target) {
  const n = numbers.length;
  const dp = Array(n + 1).fill().map(() => Array(target + 1).fill(false));

  for (let i = 0; i <= n; i++) {
    dp[i][0] = true;
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= target; j++) {
      if (numbers[i - 1] <= j) {
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - numbers[i - 1]];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  return dp[n][target];
}

// Contoh penggunaan
const numbers = [3, 34, 4, 12, 5, 2];
const target = 9;
console.log(subsetSum(numbers, target)); // Output: true

Kapan Menggunakan Subset Sum?

  • Pengambilan keputusan:Untuk masalah berbasis himpunan dengan target tertentu
  • Knapsack problem:Sebagai dasar untuk masalah optimasi seperti knapsack
  • Kriptografi:Dalam beberapa aplikasi kriptografi
  • Penjadwalan:Untuk alokasi sumber daya dengan batasan tertentu

Analisis Kompleksitas

Kompleksitas Waktu:

  • Brute Force: O(2^n)
  • Dynamic Programming: O(n*target)
  • Backtracking: O(2^n) worst case

Kompleksitas Ruang:

  • Brute Force: O(n)
  • Dynamic Programming: O(n*target)
  • Backtracking: O(n)

Kesimpulan

Subset Sum Problem adalah contoh fundamental dari masalah NP-Complete yang menunjukkan kekuatan dan keterbatasan berbagai pendekatan algoritmik. Solusi dynamic programming memberikan cara yang efisien untuk kasus dengan target yang tidak terlalu besar, sementara untuk kasus umum, masalah ini tetap menjadi tantangan dalam teori kompleksitas komputasi. Pemahaman tentang masalah ini penting sebagai dasar untuk mempelajari banyak masalah optimasi dan keputusan lainnya dalam ilmu komputer.