Algoritma (DFS)

Narasi Cerita

Pada tugas kali ini saya mendapat kasus Knapsack Problem yang harus diselesaikan menggunakan algoritma Depth First Search (DFS). Knapsack Problem adalah salah satu contoh permasalahan optimasi yang sering muncul dalam mata kuliah Algoritma dan Struktur Data. Inti dari permasalahan ini adalah bagaimana cara memilih kombinasi barang yang bisa dimasukkan ke dalam tas dengan kapasitas tertentu, sehingga nilai barang yang dibawa menjadi maksimal tetapi tidak melebihi batas kapasitas tas.

Dalam kasus saya, kapasitas tas yang diberikan adalah 10 kg, dan tersedia 5 buah barang dengan berat serta nilai yang berbeda-beda:

• 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

Strategi penyelesaian dengan algoritma DFS dilakukan dengan cara:

1. Setiap barang memiliki dua kemungkinan: dipilih atau tidak dipilih.
2. DFS akan menelusuri semua kombinasi barang secara rekursif.
3. Jika total berat kombinasi tidak melebihi kapasitas tas (10 kg), maka nilai total barang tersebut dibandingkan dengan nilai maksimum yang sudah ditemukan.
4. Setelah seluruh kemungkinan kombinasi ditelusuri, nilai terbesar akan menjadi solusi optimal.

Dari hasil penelusuran, ditemukan beberapa kombinasi menarik:

• Barang 1 + Barang 2 → total berat 9 kg, total nilai 44
• Barang 2 + Barang 4 + Barang 5 → total berat 10 kg, total nilai 43
• Barang 1 + Barang 3 → total berat 10 kg, total nilai 46

Dari ketiga contoh kombinasi di atas, nilai terbesar adalah 46, sehingga kombinasi terbaik adalah Barang 1 (6 kg, 30) dan Barang 3 (4 kg, 16).

Coding Program (Java)

public class KnapsackDFS {
    static int[] weight = {6, 3, 4, 2, 5};
    static int[] value = {30, 14, 16, 9, 20};
    static int capacity = 10;
    static int maxValue = 0;

    public static void main(String[] args) {
        dfs(0, 0, 0);
        System.out.println("Nilai maksimum yang bisa diperoleh = " + maxValue);
    }

    static void dfs(int index, int totalWeight, int totalValue) {
        // Jika semua barang sudah dicek
        if (index == weight.length) {
            if (totalWeight <= capacity) {
                maxValue = Math.max(maxValue, totalValue);
            }
            return;
        }

        // Pilih barang ke-index
        if (totalWeight + weight[index] <= capacity) {
            dfs(index + 1, totalWeight + weight[index], totalValue + value[index]);
        }

        // Tidak pilih barang ke-index
        dfs(index + 1, totalWeight, totalValue);
    }
}
  

Output Program

Nilai maksimum yang bisa diperoleh = 46
  

Codingan di atas mendefinisikan kelas DFS untuk menyelesaikan Knapsack Problem. Pertama, dibuat array weight untuk menyimpan berat barang, array value untuk menyimpan nilai barang, variabel capacity untuk kapasitas tas (10 kg), serta maxValue untuk menyimpan hasil nilai maksimum.

Pada method main, fungsi dfs(0,0,0) dipanggil yang artinya mulai dari barang pertama dengan total berat dan nilai awal 0, lalu hasil akhir nilai maksimum ditampilkan.

Fungsi dfs bekerja secara rekursif, di mana setiap barang memiliki dua pilihan: dipilih (jika total berat tidak melebihi kapasitas) atau tidak dipilih. Jika semua barang sudah dicek (index == weight.length), maka program akan mengevaluasi apakah total berat masih dalam kapasitas, dan jika iya, maxValue diperbarui dengan nilai terbesar antara nilai sebelumnya dan nilai baru.

Dengan cara ini semua kombinasi barang diperiksa, dan akhirnya didapatkan nilai maksimum 46 dengan kombinasi terbaik Barang 1 dan Barang 3.

Kesimpulan

Dari percobaan yang saya lakukan, algoritma DFS berhasil menemukan solusi optimal untuk Knapsack Problem dengan kapasitas 10 kg dan 5 buah barang. Kombinasi terbaik adalah Barang 1 (6 kg, 30) dan Barang 3 (4 kg, 16) dengan total nilai 46.

Melalui tugas ini, saya jadi lebih memahami bagaimana algoritma DFS bekerja dalam menelusuri semua kemungkinan solusi secara menyeluruh. Walaupun untuk jumlah barang yang lebih banyak DFS bisa menjadi kurang efisien karena eksplorasi cabang sangat banyak, tetapi pada kasus kecil seperti ini algoritma DFS sangat efektif dan dapat menjamin hasil optimal.

Algoritma ( Tugas 3)

Kasus Knapsack dengan Algoritma Greedy

Cerita

Bayangkan suatu hari kamu hendak melakukan perjalanan mendaki gunung bersama teman-temanmu. Kamu hanya membawa satu tas dengan kapasitas maksimal 10 kg.

Di depanmu ada lima barang yang bisa dibawa. Setiap barang punya berat dan nilai manfaat yang berbeda. Nilai ini bisa diartikan sebagai seberapa besar manfaat barang tersebut untuk perjalananmu, misalnya ada makanan, obat-obatan, pakaian hangat, atau peralatan memasak.

Daftar barang yang tersedia:

• 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 tas hanya bisa menampung 10 kg, kamu tidak bisa membawa semuanya. Maka muncul pertanyaan: “Barang mana saja yang sebaiknya dibawa agar nilai manfaatnya paling besar, tapi beratnya tidak melebihi kapasitas tas?”

Untuk menjawab pertanyaan ini, kita gunakan algoritma Greedy. Disebut Greedy (rakus) karena cara kerjanya selalu memilih barang yang paling menguntungkan saat itu juga, tanpa menunda atau memikirkan kombinasi lain.

Caranya adalah dengan menghitung rasio nilai per berat (value per weight) dari tiap barang. Barang dengan nilai per kg paling tinggi akan dipilih lebih dulu, karena dianggap paling menguntungkan dibanding berat yang dikorbankan.

Perhitungan Nilai per Kg

• Barang 1 → 30 ÷ 6 = 5.0
• Barang 2 → 14 ÷ 3 ≈ 4.67
• Barang 4 → 9 ÷ 2 = 4.5
• Barang 3 → 16 ÷ 4 = 4.0
• Barang 5 → 20 ÷ 5 = 4.0

Urutan pemilihan barang berdasarkan nilai per kg:
Barang 1 → Barang 2 → Barang 4 → Barang 3 → Barang 5

Selanjutnya kita coba masukkan barang satu per satu ke dalam tas selama masih ada ruang.

Penjelasan Coding GreedyKnapsack

Program GreedyKnapsack diawali dengan mendeklarasikan data barang dalam bentuk array dua dimensi yang berisi berat, nilai, dan nama barang. Data ini kemudian diubah menjadi List agar mudah diurutkan. Proses pengurutan dilakukan berdasarkan rasio nilai ÷ berat (value per weight) secara descending, sehingga barang dengan rasio terbesar diprioritaskan terlebih dahulu. Setelah barang terurut, program melakukan perulangan untuk memeriksa setiap barang: jika kapasitas tas masih cukup, barang tersebut dimasukkan ke tas, kapasitas berkurang sesuai beratnya, dan total nilai ditambah dengan nilai barang tersebut. Terakhir, program menampilkan hasil berupa daftar barang yang dipilih serta total nilai yang diperoleh, yaitu Barang 1 dan Barang 2 dengan total nilai 44.

Kesimpulan

Dengan algoritma Greedy, barang yang akhirnya dipilih untuk dimasukkan ke dalam tas adalah:

• Barang 1  (6 kg, nilai 30)
• Barang 2  (3 kg, nilai 14)

Total berat yang terbawa = 9 kg (tidak melebihi kapasitas 10 kg).

Total nilai yang didapat = 44.

Artinya, kamu bisa membawa dua barang tersebut dan tetap memperoleh manfaat paling besar menurut pendekatan greedy.

---

Catatan: Metode ini sederhana, cepat, dan praktis, walaupun tidak selalu menjamin hasil benar-benar optimal dalam semua kasus. Namun pada kasus kali ini, strategi greedy memberikan hasil yang cukup baik.

Interaksi Manusia dan Komputer (Tugas 2)

Kelebihan: 

• Desainnya simpel, tombol tertata rapi, dan ukurannya seimbang. 

• Ada tombol C untuk menghapus input sehingga memudahkan pengguna. 

Kekurangan :

• Belum ada fitur history, jadi hasil perhitungan sebelumnya tidak bisa dilihat kembali. 

• Tidak ada tombol akar kuadrat.

 • Belum mendukung input desimal (titik/koma).

Before 

 

 

                                               

                                          After

                                            

Untuk tata letak kalkulator tidak ada yang saya ubah karena susunannya sudah rapi dan mudah dipahami. Perubahan yang saya lakukan hanya pada bagian warna. Kali ini saya memilih warna oranye, karena warna ini terlihat cerah, hangat, dan mampu memberikan kesan semangat pada tampilan

Warna oranye saya terapkan pada tombol operator dan tombol sama dengan (=), agar hasil perhitungan terlihat lebih menonjol dan pengguna bisa lebih mudah membedakan antara tombol angka dan tombol operator. Sedangkan tombol angka tetap saya biarkan dengan warna dasar yang lebih lembut supaya fokus utama tetap pada operator dan hasil.

Selain itu, saya juga menambahkan efek hover dan shadow berwarna oranye agar ketika tombol ditekan tampilannya lebih interaktif dan tidak monoton. Dengan begitu, kalkulator terlihat lebih menarik sekaligus tetap nyaman digunakan

Saat dilakukan uji coba dengan memasukkan input yang tidak biasa, misalnya 10 ÷ 0, kalkulator awalnya menampilkan hasil Infinity. Hal ini bisa membingungkan bagi sebagian pengguna karena istilah “Infinity” tidak menjelaskan secara jelas penyebab errornya

Sebagai solusi, saya menambahkan error handling sehingga ketika pengguna membagi sebuah bilangan dengan nol, kalkulator tidak lagi menampilkan "Infinity", melainkan pesan:

👉 "Bilangan yang dibagi 0 tetap 0"

Tujuannya agar pengguna lebih mudah memahami kesalahan input, serta menghindari kebingungan dalam penggunaan kalkulator. Dengan pesan ini, sistem menjadi lebih user-friendly karena memberikan informasi yang sesuai konteks.