TUGAS INFORMATIKA

Aktivitas SAP-K11-18-U: Memahami Permasalahan (Hal 90-91)

Knapsack

1. Apakah jenis optimasi pada permasalahan knapsack? Apakah mencari minimum, ataukah
maksimum? Jelaskan!
Jawab: permasalahan knapsack pada umumnya merupakan permasalahan optimasi yang mencari
maksimum, yaitu mencari kombinasi barang dengan nilai total yang paling besar yang dapat
dimasukkan ke dalam knapsack.

2. Tentukan apa yang menjadi fungsi tujuan dari permasalahan knapsack!

Jawab: Fungsi tujuan dari permasalahan knapsack adalah untuk memilih subset barang dari himpunan
yang tersedia untuk dimasukkan ke dalam "knapsack" atau ransel dengan kapasitas terbatas,
sedemikian rupa sehingga nilai total barang yang dimasukkan maksimum.

3. Tentukan apa yang menjadi kendala pada optimasi untuk permasalahan knapsack!
Jawab: Terbatasnya total bobot yang dapat dimuat dalam knapsack.

4. Perhatikan permasalahan knapsack yang ditunjukkan oleh Tabel 2.20 berikut. Diberikan 6
buah barang, A, B, s/d F dengan bobot dan nilai sebagai berikut:

Asumsikan bahwa tas memiliki kapasitas maksimal = 24 kg.

a. Apakah pilihan mengambil barang-barang B, D, E dan F diperbolehkan sebagai solusi

sesuai dengan kendala optimasi pada permasalahan tersebut? Mengapa?
Jawab: Bobot barang B + Bobot barang D + Bobot barang E + Bobot barang F = 8 + 4 + 10 + 8 = 30. Dalam
kasus ini, total bobot barang B, D, E, dan F adalah 30 kg, yang melebihi kapasitas maksimal tas yang hanya 24
kg. Oleh karena itu, memilih barang-barang B, D, E, dan F tidak diperbolehkan sebagai solusi sesuai dengan
kendala optimasi pada permasalahan tersebut.

b. Apakah pilihan mengambil barang-barang A, D, E diperbolehkan sebagai solusi sesuai

dengan kendala optimasi pada permasalahan tersebut? Apakah fungsi tujuan mencapai nilai
optimal dengan memilih A, D dan E saja? Mengapa?
Jawab: Bobot A + Bobot D + Bobot E = 3 + 4 + 10 = 17
Dengan demikian, total bobot dari barang-barang A, D, dan E adalah 17 kg. Karena total bobot ini kurang dari
kapasitas maksimal tas (24 kg), maka pilihan mengambil barang-barang A, D, dan E diperbolehkan sebagai
solusi sesuai dengan kendala optimasi pada permasalahan tersebut.

5. Tentukan jawaban permasalahan knapsack tersebut pada soal no. 4, jika menggunakan variasi
permasalahan rational knapsack!
Jawab : Solusi dari permasalahan jika menggunakan rational knapsack yaitu dapat diperoleh
dengan menerapkan strategi greedy yaitu dengan memilih barang-barang dengan rasio nilai
terhadap bobot yang terbesar terlebih dahulu. Seperti tampak di tabel berikut:
6. Pada soal no. 4, apakah solusinya, jika digunakan variasi 0-1 knapsack? Apakah sama dengan
solusi untuk variasi rational knapsack?
Jawab : Solusi Pada variasi 0-1 knapsack, pilihan optimal didapatkan dengan memilih barang-barang A, D, F,
dan C (dengan total bobot = 20 kg) dan total nilai = 27. Untuk variasi rational knapsack, solusinya mungkin
berbeda. Pada variasi rational knapsack, setiap barang dapat dipilih sebagian berdasarkan faktor skala rasional.
Dalam hal ini, kita tidak memiliki informasi tentang faktor skala rasional yang diberikan, jadi tidak dapat
memastikan apakah solusinya akan sama atau berbeda dari variasi 0-1 knapsack.

Jawablah pertanyaan-pertanyaan berikut pada lembar jawaban/laporan PLB! (HAL92-93)

1. Tentukan pengkodean yang sesuai untuk permasalahan yang ditunjukkan pada Tabel 2.22 di
atas, dengan menggunakan skema pengkodean yang telah dijelaskan. Jelaskan!
Jawaban:
6
3 8 5 4 10 8
6 4 5 6 5 10
25

2. Tuliskan/jelaskan pada laporan analisis kalian, deskripsi permasalahan untuk contoh masukan
2 di atas!
Jawaban: Di dalam permasalahan ini ada 8 jenis barang dan menentukan nilai maksimal yang dapat di
peroleh dari kapasitas maksimal 35 kg, seperti yang ada di tabel :

3. Jelaskan dalam satu paragraf, skema pengkodean di atas, agar dapat dipahami oleh orang lain!
Jawaban: Skema pengkodean untuk masalah ini melibatkan representasi data dalam bentuk dua daftar, satu
untuk bobot barang dan satu lagi untuk nilai barang. Setiap barang memiliki bobot dan nilai tertentu yang
diinputkan, dan tujuan utamanya adalah untuk memilih kombinasi barang yang memberikan nilai maksimal
tanpa melebihi batas bobot yang diizinkan. Dengan menggunakan teknik optimasi seperti algoritma greedy atau
dynamic programming, masalah ini dapat diselesaikan secara efektif untuk mencari solusi terbaik.

4. Mungkinkah sebuah representasi data tidak valid/tidak sesuai?Berikan contohnya, dan

tuliskan penjelasannya pada laporan analisis!
Jawaban: sangat mungkin sebuah representasi data tidak valid atau tidak sesuai dengan permasalahan yang
dihadapi. Beberapa kondisi yang menyebabkan data tidak valid atau tidak sesuai dalam masalah knapsack,
misalnya bobot atau nilai negatif, kapasitas maksimum negatif, dan jumlah barang yang tidak konsisten.

Aktivitas SAP-K11-20-U: Merancang Algoritma

Penyelesaian Masalah Knapsack (HAL 93-94)

1. Untuk permasalahan rational knapsack, tentukan apakah strategi greedy ataukah dynamic
programming yang sesuai untuk diterapkan? Jelaskan pada laporan analisis kamu, bagaimana
strategi greedy atau dynamic programming dapat diterapkan pada permasalahan rational
knapsack!
Jawaban:
Untuk permasalahan rational knapsack, di mana item dapat dibagi-bagi (fractional), strategi yang
paling sesuai adalah greedy approach. Pendekatan ini melibatkan memilih item berdasarkan
rasio nilai terhadap berat (atau ukuran). Dengan kata lain, kita memilih item dengan rasio nilai
per unit berat tertinggi terlebih dahulu, dan melanjutkan dengan item-item lainnya hingga
kapasitas knapsack terisi.
Alasan Mengapa Greedy Approach Sesuai:
- Pada knapsack rasional, kita dapat mengambil bagian dari item. Ini berarti bahwa kita
tidak perlu memikirkan berbagai kombinasi seperti dalam 0-1 knapsack.
- Greedy approach berfungsi dengan baik dalam kasus ini karena kita bisa selalu membuat
keputusan lokal terbaik (mengambil item dengan rasio terbaik) yang akan menghasilkan solusi
optimal global untuk masalah ini.

2. Untuk permasalahan 0−1 knapsack, tentukan apakah strategi greedy ataukah dynamic
programming yang sesuai untuk diterapkan?
Jawaban:
Strategi yang Sesuai: Dynamic Programming Approach
Untuk permasalahan 0-1 knapsack, di mana item harus diambil seluruhnya atau tidak sama
sekali, strategi yang paling sesuai adalah dynamic programming. Pendekatan ini melibatkan
penggunaan tabel untuk menyimpan hasil subproblem dan menghindari perhitungan yang
berulang.
Alasan Mengapa Dynamic Programming Sesuai:
- Dalam masalah 0-1 knapsack, kita perlu mempertimbangkan berbagai kombinasi item
yang mungkin diambil untuk mencapai kapasitas maksimum. Dynamic programming membantu
dalam menyimpan hasil subproblem sehingga kita tidak perlu menghitung ulang untuk
subproblem yang sama.
- Ini memungkinkan kita untuk mengeksplorasi solusi yang lebih efisien daripada
eksplorasi brute-force yang sangat mahal secara komputasi.

3. Tuliskan dalam notasi pseudocode algoritma yang sesuai untuk menyelesaikan permasalahan
rational knapsack menggunakan strategi yang Anda pilih pada bagian nomor 1!
Jawaban:
function zeroOneKnapsack(values, weights, capacity): n
= length(values) dp = array of size (n+1) x
(capacity+1) initialized to 0 for i from 1 to n:
for w from 0 to capacity:
if weights[i-1] <= w:
dp[i][w] = max(dp[i-
1][w], dp[i-1][w -
weights[i-1]] +
values[i-1])
else: dp[i][w] = dp[i-
1][w]
return dp[n][capacity]

4. [Opsional] Tuliskan dalam notasi _pseudocode_ algoritma yang sesuai untuk menyelesaikan
permasalahan 0-1 knapsack menggunakan strategi yang Anda pilih pada bagian nomor 2!
Jawaban:
function zeroOneKnapsack(values, weights, capacity): n
= length(values) dp = array of size (n+1) x
(capacity+1) initialized to 0
for i from 1 to n:
for w from 0 to capacity:
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
else: dp[i][w] = dp[i-
1][w]
return dp[n][capacity]
Dalam pseudocode di atas:
- `values` adalah daftar nilai item.
- `weights` adalah daftar berat item.
- `capacity` adalah kapasitas maksimum knapsack.
- Untuk knapsack rasional, kita memanfaatkan strategi greedy dengan memanfaatkan rasio
nilai/berat.
- Untuk knapsack 0-1, kita menggunakan dynamic programming untuk menghindari perhitungan
yang berulang dan memastikan solusi optimal.

Ayo Renungkan! (HAL 98)

1. Apa yang kalian rasakan saat membuat suatu program di Praktik Lintas Bidang ini? Sangat
Antusias dan bingung saat membuat percodingan.

2. Apakah program yang kalian buat dapat membantu kalian atau orang lain? Kemungkinan
besar iya

3. Apakah solusi yang telah kalian buat dapat dimanfaatkan untuk menyelesaikan masalah lain
yang sejenis? Iya

4. Adakah pengembangan lebih lanjut (enhancing) yang terpikir oleh kalian agar program
menjadi lebih bermanfaat? Belum

5. Apa yang kalian rasakan saat memeriksa solusi algoritma dan program teman kalian? Masih agak bingung
untuk memahaminya

6. Apa yang kalian rasakan saat solusi algoritma dan program kalian diperiksa oleh teman
kalian? Kurang yakin karna kita belum sepenuhnya mengerti dengan knapscak

7. Pelajaran paling parmesan apa yang kalian dapatkan dari aktivitas latihan ini? Belajar perkodingan dan
belajar untuk tidak gampang menyerah