Algoritma (BFS)

Knapsack Problem dengan BFS

Narasi Cerita

Pada tugas ini saya mencoba menyelesaikan kasus Knapsack Problem dengan menggunakan algoritma BFS (Breadth First Search). Kasus yang saya pilih adalah memilih barang-barang ke dalam sebuah tas dengan kapasitas maksimum 10 kg. Terdapat 5 barang yang tersedia, masing-masing memiliki berat dan nilai yang berbeda. Tujuannya adalah menentukan kombinasi barang yang memberikan nilai total paling besar, tanpa melebihi kapasitas tas.

Data barang yang digunakan adalah:

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

Saya memulai dari state awal, yaitu tas dalam keadaan kosong dengan berat 0 dan nilai 0. Kemudian dengan menggunakan algoritma BFS, setiap langkah saya menjelajahi kemungkinan “skip” atau “ambil” suatu barang. Karena BFS menelusuri semua kemungkinan secara menyeluruh, maka setiap kombinasi barang bisa dievaluasi hingga ditemukan yang paling optimal.

Dari hasil eksplorasi BFS melalui program Java, saya mendapatkan bahwa kombinasi terbaik adalah dengan mengambil Barang 1 (6 kg, nilai 30) dan Barang 3 (4 kg, nilai 16). Total beratnya tepat 10 kg dan total nilainya adalah 46, yang merupakan nilai terbesar dari semua kemungkinan kombinasi barang yang lain.

Dari percobaan ini saya belajar bahwa BFS sangat membantu dalam mencari solusi optimal karena algoritma ini menelusuri semua jalur kemungkinan tanpa ada yang terlewat. Awalnya saya menduga kombinasi terbaik adalah Barang 2, Barang 3, dan Barang 4 (nilai 39), tetapi setelah diuji dengan BFS ternyata masih ada kombinasi yang lebih optimal yaitu Barang 1 dan Barang 3 dengan nilai 46.

Kode Program Java

Knapsack Problem Menggunakan BFS

Pada tugas kali ini saya mencoba menyelesaikan Knapsack Problem dengan memakai algoritma BFS (Breadth First Search). Intinya, saya harus memilih barang-barang yang bisa dimasukkan ke dalam tas dengan kapasitas maksimal 10 kg, supaya nilai totalnya bisa sebesar mungkin.

Data barang yang saya pakai ada 5, masing-masing punya berat dan nilai berbeda, yaitu:

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

Saya mulai dari kondisi awal yaitu tas kosong (berat 0, nilai 0). Dengan algoritma BFS, setiap langkah selalu ada dua kemungkinan: apakah barangnya di-skip atau barangnya diambil (kalau masih muat). Karena BFS ini telusurannya level by level, semua kombinasi barang bisa dicek satu per satu.

Hasil akhirnya cukup menarik, karena setelah semua kombinasi diuji, ternyata kombinasi terbaik adalah dengan mengambil Barang 1 dan Barang 3. Total beratnya pas 10 kg dan nilai totalnya 46. Jadi kombinasi ini lebih bagus dibandingkan pilihan lain yang sebelumnya saya kira optimal.

Dari tugas ini saya jadi paham kalau BFS bukan cuma dipakai di pencarian jalur, tapi juga bisa dipakai buat nyari solusi optimal di kasus kayak gini. Walaupun agak boros karena semua kemungkinan dicoba, tapi untuk jumlah barang yang sedikit masih oke dan pasti ketemu hasil maksimalnya.

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.

Algoritma

Pendahuluan

Apa itu Algoritma Pemrograman?
Algoritma pemrograman adalah serangkaian langkah logis yang dirancang untuk memecahkan masalah tertentu dalam cara yang sistematis. Langkah-langkah ini berfungsi sebagai intruksi bagi komputer yang menjalankan tugas tertentu, misalnya mengelolah data atau menampilkan informasi.

Dengan adanya algoritma, aplikasi bisa berjalan lebih cepat dan terhindar dari error. Tanpa algoritma yang tepat, aplikasi atau program akan berjalan sangat lambat atau memberikan hasil yang tidak akurat.

Cara Kerja Algoritma Pemrograman

Cara kerja algoritma pemrograman pada dasarnaya melibatkan tiga tahap utama, yaitu input, proses, dan output. Berikut penjelasan dan contohnya dalam penggunaan sehari-hari:

1. Bidang : Pendidikan

Contoh Permasalahan : Keterlambatan Pengumpulan Tugas Mahasiswa

Tugas :

Cari masalah dalam suatu bidang tertentu, dan jabarkan proses tersebut dalam prosedur langkah demi langkah bagaimana kira-kira Anda akan melakukannya dalam menyelesaikan masalah? Identifikasi Input, proses dan Outputnya!

Renungkan apa alasan kenapa algoritma Anda dapat efektif? Dan sekitarnya terjadi kebutuhan yang mengharuskan Anda untuk mengubah Inputnya apakah prosedur - clemi - prosedur yang Anda buat akan berubah secara keseluruhan? Jelaskan bagian mana saja dari prosedur yang perlu di ubah?

Bagaimana Anda bisa memastikan bahwa algoritma yang Anda akan kembangkan tidak hanya efisien dan efektif tetapi juga adil dan transparan?

1.

Langkah-langkah yang bisa dilakukan menurut saya :

• Pertama kita harus tau dulu masalahnya. Beberapa teman, bahkan termasuk saya sendiri pernah telat mengumpulkan tugas (kadang lebih suka deadline)
• Setelah itu kita bisa coba cari tau alasannya dengan berdiskusi bersama teman-teman, ternyata ada yang bilang lupa, susah membagi waktu bahkan kadang terkendala di jaringan apalagi yang rumahnya agar terpencil otomatis jaringan susah didapatkan sehingga bisa menjadi salah satu faktor penghambat mengumpulkan tugas secara online.
• Nah dari situ dianalisis kalau sebenarnya kebanyakan mahasiswa bukan malas, tapi belum bisa memanajemen waktu dengan baik.
• Selelah mengamati masalah tersebut solusi yang bisa kita ambil yaitu membuat pengigat di grup wa kelas, berupa jadwal yang jelas
• Jadi biar tugas tersebut bukan cuma tugas ketua tingkat tapi siapa saja bisa buat saling mengigatkan
• Terakhir kita bisa mengevaluasi, dilihat apakah setelah ada pengigat masih banyak yang telat atau sudah berkurang.

Input => Data keterlambatan dan alasan kenapa telat
Proses => Analisis penyebab, buat solusi, kemudian dijalankan
Output => Mahasiswa tepat waktu bahkan lebih awal

2.

Menurut saya algoritma ini efektif karena langkanya jelas dan ada evaluasi di akhir. Kalau input berubah, prosedurnya nggak perlu diganti semua, cukup diawal saja kayak indentifikasi masalah, ngumpulin data, sama analisis. Sisanya masih sama, cuma di sesuaikan masalah barunya.

3.

• Efisien: Algoritma cuma pake data penting aja, kayak deadline sama jam ngumpulin tugas, jadi prosesnya cepat dan tidak ribet
• Efektif: Hasilnya langsung keliatan apakah tugas tepat waktu atau telat, jadi dosen tidak perlu ngecek manual lagi
• Adil: Aturannya sama buat semua mahasiswa, jadi tidak ada pilih kasih
• Trasparan: Sistem nunjukin jelas, misalnya "Deadline 23:59, dikumpul 00:05 telat 6 menit", jadi mahasiswa bisa lihat buktinya.

FISIKA ELEKTRONIKA

 

WSBI

 

DDP

 

Foto

 

                                                            

Biodata

• BIODATA

Nama               : Nurfadila Amir

Tanggal Lahir  :18 April 2005

Alamat             : Tandassura

Kelas                : D

Prodi                 :Informatika

Fakultas            :Teknik

Universitas       :Sulawesi Barat