Tugas 3 Algoritma – Kasus Knapsack dengan Algoritma Greedy

 

Cerita Kasus

Bayangkan saya memiliki sebuah tas dengan kapasitas 10 kg. Ada 5 barang di depan saya, masing-masing dengan berat dan nilai yang berbeda. Saya ingin membawa barang dengan total nilai terbesar, tetapi beratnya tidak boleh lebih dari kapasitas tas.

Data barang yang tersedia adalah:

• 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)

Kode Program 

import java.util.*;

class Item {

    int weight;

    int value;

    double ratio;

    Item(int w, int v) {

        weight = w;

        value = v;

        ratio = (double) v / w;

    }

}

public class KnapsackGreedy {

    public static void main(String[] args) {

        int capacity = 10;

        Item[] items = {

            new Item(6, 30), 

            new Item(3, 14), 

            new Item(4, 16), 

            new Item(2, 9), 

            new Item(5, 20)  

        };

        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));

        int totalWeight = 0;

        int totalValue = 0;

        List<Item> chosen = new ArrayList<>();

        for (Item item : items) {

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

                chosen.add(item);

                totalWeight += item.weight;

                totalValue += item.value;

            }

        }

        System.out.println("Barang yang dipilih (berat, nilai):");

        for (Item item : chosen) {

            System.out.println("- (" + item.weight + " kg, " + item.value + ")");

        }

        System.out.println("Total berat = " + totalWeight + " kg");

        System.out.println("Total nilai = " + totalValue);

    }

}