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

 

Narasi Cerita

Bayangkan kamu hendak pergi berkemah dengan sebuah tas berkapasitas 10 kg.
Kamu memiliki 5 barang dengan berat dan nilai yang berbeda:

1. Barang 1: (6 kg, nilai 30)
2. Barang 2: (3 kg, nilai 14)
3. Barang 3: (4 kg, nilai 16)
4. Barang 4: (2 kg, nilai 9)
5. Barang 5: (5 kg, nilai 20)

Tujuanmu adalah membawa barang-barang yang total nilainya paling besar, tanpa melebihi kapasitas tas (10 kg).

Masalah ini dapat diselesaikan dengan algoritma BFS (Breadth-First Search). Ide utamanya adalah:

• Setiap node menyatakan kondisi (index barang, berat saat ini, nilai saat ini, daftar barang yang dipilih).
• Dari setiap node, ada dua kemungkinan: mengambil barang atau melewatkannya.
• BFS akan menelusuri semua kemungkinan kombinasi secara level demi level.
• Di akhir, kita pilih kombinasi dengan nilai terbesar.

Kode Program :

import java.util.*;

class state {

    int index;

    int totalWeight;

    int totalValue;

    String chosen;

    public state(int index, int totalWeight, int totalValue, String chosen) {

        this.index = index;

        this.totalWeight = totalWeight;

        this.totalValue = totalValue;

        this.chosen = chosen;

    }

}

public class knapsackbfs {

    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;

        int maxValue = 0;

        int bestWeight = 0;

        String bestChoice = "";

        Queue<state> queue = new LinkedList<>();

        queue.add(new state(1, 0, 0, "")); // mulai dari barang ke-1

        while (!queue.isEmpty()) {

            state current = queue.poll();

            if (current.index > items.size()) {

                if (current.totalValue > maxValue) {

                    maxValue = current.totalValue;

                    bestWeight = current.totalWeight;

                    bestChoice = current.chosen;

                }

                continue;

            }

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

            int weight = data[0];

            int value = data[1];

            queue.add(new state(current.index + 1,

                    current.totalWeight,

                    current.totalValue,

                    current.chosen));

            if (current.totalWeight + weight <= capacity) {

                queue.add(new state(current.index + 1,

                        current.totalWeight + weight,

                        current.totalValue + value,

                        current.chosen + "Barang" + current.index +

                                "(berat=" + weight + ", nilai=" + value + ") "));

            }

        }

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

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

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

    }

Output :

}