Penyelesaian Knapsack dengan DFS (Java)

Penyelesaian Knapsack dengan DFS

Menjelaskan tentang konsep, implementasi, dan contoh penggunaan algoritma Depth-First Search (DFS) dalam pemrograman.

Konsep DFS (Depth First Search)

Depth First Search (DFS) adalah salah satu algoritma pencarian pada graf. Prinsipnya adalah menjelajah graf sedalam mungkin terlebih dahulu, baru kemudian mundur (backtrack) untuk menjelajah simpul lainnya.

DFS untuk Knapsack

DFS adalah metode pencarian rekursif yang menelusuri semua kemungkinan keputusan sampai ke ujung (daun pohon keputusan).

Pada kasus Knapsack Problem, setiap barang punya 2 pilihan:

1. Diambil (jika kapasitas masih cukup).
2. Tidak diambil.

DFS menelusuri pohon semua kombinasi barang (total kemungkinan 𝑛2).

Dari semua solusi yang valid (berat ≤ kapasitas), dipilih nilai total terbesar.

Pseudocode DFS

fungsi DFS(index, totalBerat, totalNilai, daftarBarang):
    jika index == jumlahBarang:
        jika totalBerat ≤ kapasitas:
            periksa apakah totalNilai > nilaiMaksimum
                jika iya, simpan totalNilai sebagai nilaiMaksimum
                simpan daftarBarang sebagai kombinasi terbaik
        kembali

    // Pilihan 1: tidak ambil barang ke-index
    DFS(index+1, totalBerat, totalNilai, daftarBarang)

    // Pilihan 2: ambil barang ke-index jika muat
    jika totalBerat + berat[index] ≤ kapasitas:
        tambahkan barang[index] ke daftarBarang
        DFS(index+1, totalBerat + berat[index], totalNilai + nilai[index], daftarBarang)
        hapus barang[index] dari daftarBarang (backtracking)

Implementasi Java

import java.util.*;

public class KnapsackDFS {
    // Data barang (berat, nilai)
    static int[][] items = {
        {6, 30}, // Barang 1: berat 6, nilai 30
        {3, 14}, // Barang 2
        {4, 16}, // Barang 3
        {2, 9},  // Barang 4
        {5, 20}  // Barang 5
    };
    static int capacity = 10;  // Kapasitas tas
    
    static int maxValue = 0;                 // Nilai maksimum
    static List bestCombination = new ArrayList<>(); // Barang terbaik

    public static void main(String[] args) {
        dfs(0, 0, 0, new ArrayList<>());

        System.out.println("Nilai maksimum: " + maxValue);
        System.out.println("Barang terpilih: " + bestCombination);
    }

    static void dfs(int index, int currentWeight, int currentValue, List chosen) {
        // Basis: jika sudah cek semua barang
        if (index == items.length) {
            if (currentWeight <= capacity && currentValue > maxValue) {
                maxValue = currentValue;
                bestCombination = new ArrayList<>(chosen);
            }
            return;
        }

        // Pilihan 1: tidak ambil barang[index]
        dfs(index + 1, currentWeight, currentValue, chosen);

        // Pilihan 2: ambil barang[index] jika muat
        int w = items[index][0];
        int v = items[index][1];
        if (currentWeight + w <= capacity) {
            chosen.add(index + 1); // simpan nomor barang
            dfs(index + 1, currentWeight + w, currentValue + v, chosen);
            chosen.remove(chosen.size() - 1); // backtrack
        }
    }
}

Hasil Eksekusi

Nilai maksimum: 59
Barang terpilih: [2, 3, 4, 5]

Penjelasan Hasil

DFS menelusuri semua kombinasi barang.

Dari 32 kombinasi (karena 5 barang → 2 5), yang valid dipilih.

Kombinasi terbaik adalah Barang 2, 3, 4, dan 5 dengan:

1. Total berat = 3 + 4 + 2 + 5 = 10 kg
2. Total nilai = 14 + 16 + 9 + 20 = 59