Algoritma Brute Force Untuk Menemukan Kombinasi Barang Yang Tidak Lebih Dari 10kg dan Memiliki Nilai Tertinggi

Kasus Cerita :

Kamu memiliki tas dengan kapasitas 10 kg. Tersedia 5 barang dengan berat dan nilai berbeda: Barang 1 (6 kg, 30), Barang 2 (3 kg, 14), Barang 3 (4 kg, 16), Barang 4 (2 kg, 9), dan Barang 5 (5 kg, 20). Karena kapasitas terbatas, kamu harus memilih kombinasi barang yang memberikan nilai tertinggi tanpa melebihi 10 kg. Untuk menemukan pilihan terbaik, digunakan algoritma brute force, yaitu dengan mencoba semua kemungkinan kombinasi barang, menghitung total berat dan nilainya, lalu memilih kombinasi dengan nilai tertinggi yang masih sesuai kapasitas.

Ringkasan Poin :

• Kapasitas tas: 10 kg.

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

• Brute force: cek semua kombinasi, hitung berat & nilai, singkirkan yang lebih besar dari 10 kg.

Kode Program :

public class KnapsackBruteForce{

    public static void main(String[] args) {

        int[] weight = {6, 3, 4, 2, 5};

        int[] value  = {30, 14, 16, 9, 20};

        int W = 10;

        int n = weight.length;

        int maxValue = 0;

        String bestSet = "";

        

        for (int mask = 0; mask < (1 << n); mask++) {

            int totalWeight = 0, totalValue = 0;

            StringBuilder items = new StringBuilder();

            for (int i = 0; i < n; i++) {

                if ((mask & (1 << i)) != 0) {

                    totalWeight += weight[i];

                    totalValue += value[i];

                    items.append("Barang ").append(i + 1).append(" ");

                }

            }

            if (totalWeight <= W && totalValue > maxValue) {

                maxValue = totalValue;

                bestSet = items.toString();

            }

        }

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

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

        System.out.println("Kapasitas tas    : " + W + " kg");

    }

}

 Output :