Penerapan Algoritma DFS dalam Kasus Knapsack (Pemilihan Barang ke Tas)

Kasus: 

Suatu hari kamu ingin bepergian dengan tas berkapasitas 10 kg.
Di rumah ada 5 barang dengan berat dan nilai berbeda:

• Barang 1: Berat 6 kg, Nilai 30

• Barang 2: Berat 3 kg, Nilai 14

• Barang 3: Berat 4 kg, Nilai 16

• Barang 4: Berat 2 kg, Nilai 9

• Barang 5: Berat 5 kg, Nilai 20

Karena kapasitas tas hanya 10 kg, kamu harus pintar memilih kombinasi barang agar total nilai maksimal tetapi tidak melebihi 10 kg.

Untuk mencari solusinya, kita gunakan DFS (Depth-First Search). DFS akan menelusuri semua kemungkinan kombinasi barang (ambil / tidak ambil), lalu memilih yang terbaik.

Kode Program : 

import java.util.HashMap;

public class KnapsackDFSHashMap {

    static int maxValue = 0;

    static int bestWeight = 0;

    static String bestChoice = "";

    public static void main(String[] args) {

        HashMap<Integer, int[]> items = new HashMap<>();

        items.put(1, new int[]{6, 30});  

        items.put(2, new int[]{3, 14}); 

        items.put(3, new int[]{4, 16});  

        items.put(4, new int[]{2, 9});   

        items.put(5, new int[]{5, 20});  

        int capacity = 10;

        dfs(1, 0, 0, "", items, capacity);

        System.out.println();

        System.out.println("Kombinasi barang terbaik: " + bestChoice);

        System.out.println("Total Berat: " + bestWeight + " kg");

        System.out.println("Total Nilai: " + maxValue);

    }

    public static void dfs(int index, int currentWeight, int currentValue,

            String chosen, HashMap<Integer, int[]> items, int capacity) {

               if (currentWeight > capacity) return;

        if (index > items.size()) {

            if (currentValue > maxValue) {

                maxValue = currentValue;

                bestWeight = currentWeight;

                bestChoice = chosen;

            }

            return;

        }

        int[] data = items.get(index);

        int weight = data[0];

        int value = data[1];

        dfs(index + 1,

            currentWeight + weight,

            currentValue + value,

            chosen + "Barang" + index + "(berat=" + weight + ", nilai=" + value + ") ",

            items, capacity);

        dfs(index + 1,

            currentWeight,

            currentValue,

            chosen,

            items, capacity);

    }

}