LKPD 2: Misi Pencari Harta Karun (Knapsack Problem)
Nama Kelompok: .......................................
Kamu menemukan 5 buah harta karun. Ranselmu hanya mampu menampung beban maksimal 15 kg.
No Harta Karun Berat (kg) Nilai (juta Rupiah)
1 Mahkota 5 8
2 Patung Emas 10 12
3 Pedang Permata 7 9
4 Guci Antik 4 5
5 Koin Kuno 2 3
Tugas:
Isilah tabel di bawah ini berdasarkan strategi yang diminta untuk mendapatkan nilai setinggi mungkin!
Barang Total Berat (Max 15 Total Nilai (juta
Strategi
Terpilih kg) Rp)
1. Nilai Tertinggi Dulu
2. Barang Teringan
Dulu
3. Kombinasi
Terbaikmu
Analisis:
Berdasarkan tabel di atas, strategi manakah yang memberikan solusi paling optimal (nilai tertinggi)?
Mengapa?
................................................................................................................................................
C. Asesmen Akhir (Sumatif)
I. Pilihan Ganda (10 Soal)
Pilihlah satu jawaban yang paling tepat!
1. Proses untuk menemukan solusi terbaik dari semua kemungkinan yang ada disebut...
a. Algoritma b. Efisiensi c. Optimasi d. Dekomposisi
2. Seorang programmer membuat dua program untuk mengurutkan data. Program A selesai dalam
1 detik, Program B selesai dalam 3 detik. Aspek yang dibandingkan di sini adalah...
a. Optimasi b. Efisiensi waktu c. Efisiensi memori d. Kompleksitas
3. Masalah mencari rute terpendek untuk mengunjungi banyak kota dan kembali ke awal adalah
contoh dari...
a. Knapsack Problem b. Sorting Problem c. Searching Problem d. Traveling Salesperson
Problem
4. Tujuan utama dari Knapsack Problem adalah...
a. Meminimalkan total berat b. Memaksimalkan jumlah barang c. Memaksimalkan total nilai d.
Mengisi ransel sampai penuh
5. Memecah masalah besar menjadi beberapa masalah kecil yang lebih mudah diselesaikan adalah
teknik...
a. Optimasi b. Abstraksi c. Dekomposisi d. Pengenalan Pola
6. Dalam pemodelan komputasional, aturan atau keterbatasan yang ada dalam sebuah masalah
disebut...
a. Variabel b. Tujuan c. Batasan d. Solusi
7. Sebuah aplikasi ojek online menyarankan rute tercepat dengan memperhitungkan kemacetan.
Aplikasi tersebut sedang menyelesaikan masalah...
a. Optimasi b. Klasifikasi c. Privasi data d. Keamanan jaringan
8. Manakah yang BUKAN merupakan contoh masalah optimasi?
a. Mengatur jadwal pelajaran agar tidak bentrok.
b. Memilih bahan bangunan termurah untuk membangun rumah.
c. Menyimpan file tugas ke dalam folder di komputer.
d. Menyusun barang di gudang agar hemat tempat.
9. Strategi greedy dalam Knapsack Problem dengan memilih barang bernilai tertinggi lebih dulu
tidak selalu optimal karena...
a. Barang bernilai tinggi biasanya paling ringan.
b. Barang bernilai tinggi bisa jadi memakan terlalu banyak kapasitas.
c. Strategi greedy selalu menghasilkan solusi yang salah.
d. Kapasitas ransel tidak mempengaruhi hasil.
10. Langkah pertama dalam merumuskan persoalan menjadi model komputasional adalah...
a. Mencari variabelnya b. Menentukan batasannya c. Mengidentifikasi tujuannya d. Menulis
kodenya
II. Esai (5 Soal)
1. Jelaskan dengan bahasamu sendiri, apa perbedaan mendasar antara optimasi dan efisiensi! Berikan
contoh.
2. Kamu adalah ketua panitia acara class meeting di sekolah. Ada 3 lomba (basket, futsal, catur) yang
harus selesai dalam satu hari (08:00 - 15:00) dengan 3 lapangan yang tersedia. Buatlah model
komputasional untuk masalah penjadwalan ini (tentukan Tujuan, Variabel, dan Batasannya)!
3. Lihat peta TSP pada LKPD 1. Jika ada aturan tambahan "Lokasi C harus dikunjungi tepat setelah
lokasi A", bagaimana hal itu mengubah solusimu? Rute mana yang menjadi optimal sekarang?
4. Mengapa strategi greedy (misal: mengambil barang paling berharga dulu) tidak selalu
menghasilkan solusi optimal pada Knapsack Problem? Jelaskan dengan sebuah contoh!
Menurutmu, di bidang industri atau pekerjaan apa konsep optimasi sangat penting untuk diterapkan?
Berikan satu contoh dan jelaskan alasannya!