HALLO …
Kali
ini saya akan memposting mengenai solusi permasalahan knapsack problem dengan
greedy. Tulisan ini dibuat untuk menambah nilai pada tugas 3 (Soal Bonus) mata
kuliah Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST, MT .
Fakultas Teknik, Prodi Teknik Informatika, UHAMKA.->
Knapsack Problem dengan Greedy
Sebelum
kita menuju ke sebuah contoh soal / studi kasus knapsack problem. Terlebih dahulu
kita harus tau definisi knapsack problem.
Apa
itu Knapsack Problem ?
Knapsack
problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari
sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit
masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang
maksimum.
Dalam
kehidupan sehari-hari, kita sering dipusingkan dengan media penyimpanan yang
terbatas padahal kita diharuskan menyimpan beberapa objek kedalam media
tersebut.
Bagaimana kita mengatur objek apa saja yang dipilih dan seberapa besar objek tersebut disimpan?
Dari permasalahan tersebut, munculah suatu permasalahan yang dikenal dengan “Permasalahan Knapsack” atau lebih dikenal dengan “Knapsack Problem”. Masalah Knapsack merupakan suatu permasalahan bagaimana memilih objek dari sekian banyak dan berapa besar objek tersebut akan disimpan sehingga diperoleh suatu penyimpanan yang optimal dengan memperhatikan objek yang terdiri dari n objek (1,2,3,…) dimana setiap objek memiliki bobot (Wi) dan profit (Pi) dengan memperhatikan juga kapasitas dari media penyimpanan sebesar M dan nilai probabilitas dari setiap objek (Xi).
Bagaimana kita mengatur objek apa saja yang dipilih dan seberapa besar objek tersebut disimpan?
Dari permasalahan tersebut, munculah suatu permasalahan yang dikenal dengan “Permasalahan Knapsack” atau lebih dikenal dengan “Knapsack Problem”. Masalah Knapsack merupakan suatu permasalahan bagaimana memilih objek dari sekian banyak dan berapa besar objek tersebut akan disimpan sehingga diperoleh suatu penyimpanan yang optimal dengan memperhatikan objek yang terdiri dari n objek (1,2,3,…) dimana setiap objek memiliki bobot (Wi) dan profit (Pi) dengan memperhatikan juga kapasitas dari media penyimpanan sebesar M dan nilai probabilitas dari setiap objek (Xi).
Jenis-Jenis
Knapsack Problem:
- 0/1 Knapsack problem
Setiap barang hanya tersedia 1 unit, take it or leave it. - Fractional Knapsack problem
Barang boleh dibawa sebagian saja (unit dalam pecahan). Versi problem ini menjadi masuk akal apabila barang yang tersedia dapat dibagi-bagi misalnya gula, tepung, dan sebagainya. - Bounded Knapsack problem
Setiap barang tersedia sebanyak N unit (jumlahnya terbatas). - Unbounded Knapsack problem
Setiap barang tersedia lebih dari 1 unit, jumlahnya tidak terbatas
Cara menyelesaikan
masalah Knapsack adalah
1.
Tentukan Fungsi Tujuan, yaitu mencari nilai maximum dari jumlah hasil perkalian
antara nilai profit (Pi) dengan nilai probabilitas (Xi)
Maximum ∑Pi.Xi
Maximum ∑Pi.Xi
2.
Tentukan Fungsi Pembatas, yang merupakan hasil penjumlahan dari perkalian
antara bobot (Wi) dengan nilai probabilitas (Xi) yang tidak boleh melebihi dari
kapasitas media penyimpanan (M)
∑Wi.Xi≤M, dimana
0≤Xi≤1, Pi>0, Wi>0
Dari ke-2 cara di atas berarti kita harus mengetahui
1. Jumlah objek (n)
2. Bobot setiap objek (Wi)
3. Profit setiap objek (Pi)
4. Probabilitas setiap objek (Xi), dan
5. Kapasitas media penyimpanan (M)
∑Wi.Xi≤M, dimana
0≤Xi≤1, Pi>0, Wi>0
Dari ke-2 cara di atas berarti kita harus mengetahui
1. Jumlah objek (n)
2. Bobot setiap objek (Wi)
3. Profit setiap objek (Pi)
4. Probabilitas setiap objek (Xi), dan
5. Kapasitas media penyimpanan (M)
Proses Kerja Metode Greedy.
Menyelesaikan
suatu masalah dengan beberapa fungsi pembatas untuk mencapai satu fungsi
tujuan. Jadi dalam penyelesaiannya harus ditentukan mana sebagai fungsi pembatas
dan mana sebagai fungsi tujuan.
Metode greedy memiliki 3 pilihan strategi pengangkutan,
yaitu:
1. Greedy by Profit
Strategi ini mengharapkan keuntungan maksimal dengan cara
memasukan barang atau objek dengan nilai keuntungan terbesar terlebih dahulu ke
dalam kantong atau knapsack. Jadi strategi ini hanya mempertimbangkan jumlah
keuntungan dari sekumpulan barang, dengan catatan berat barang yang akan dibawa
tidak melebihi kapasitas kantong yang kita miliki.
2. Greedy by weight
Pada strategi ini, kita berusaha memasukan barang
sebanyak-banyaknya kedalam kantong, jadi barang atau objek yang dimasukan
terlebih dahulu adalah barang dengan bobot paling ringan terlebih dahulu,
dengan harapan dengan banyaknya barang atau objek yang terangkut kita bisa
mendapatkan keuntungan sebesar-besarnya.
3. Greedy by density
Strategi ini mengharapkan keuntungan sbesar-besarnya dengan
memasukan barang yang memiliki keuntungan per unit terbesar (Pi/Wi)
terlebih dahulu kedalam kantong.
Permasalahan
ini dapat diselesaikan dengan 3 cara, yaitu :1. Matematika, 2. Greedy, dan 3.
Algoritma Greedy.
Dalam
kasus ini penulis hanya mencoba menyelesaikan dengan cara Greedy. Metode Greedy
merupakan salah satu cara untuk mendapatkan solusi optimal dalam proses penyimpanan.
Pada metode ini untuk mendapatkan solusi optimal dari permasalahan yang mempunyai
dua kriteria yaitu Fungsi Tujuan/Utama dan Nilai Pembatas (Constrain). Fungsi Tujuan
hanya terdiri atas satu fungsi sedangkan Fungsi Pembatas dapat terdiri atas
lebih dari satu fungsi.
Berikut sebuah contoh
permasalahan dengan solusi knapsack dengan metode Greedy
Contoh 1 :
Diketahui 3 barang yang akan
disimpan pada suatu tempat yang memiliki kapasitas maksimal sebesar 20 Kg.
Berat masing-masing barang adalah 18 Kg, 15 Kg, dan 10 Kg dimana setiap barang
memiliki profit sebesar masing-masing 25, 24, dan 15. Tentukan barang mana saja
yang dapat disimpan ke dalam tempat penyimpanan sehingga diperoleh nilai profit
yang maksimal.
Jawab :
Jawab :
2. Cara greedy
n = 3, (1, 2, 3) à objek
M = 20 à kapasitas
(W1, W2, W3) = (18, 15, 10)
(P1, P2, P3) = (25, 24, 15)
Nilai probabilitas 0 ≤ Xi ≤ 1
Kriteria greedy :
a. Pilih objek dengan nilai profit terbesar (Pi)
Susun data sesuai kriteria:
(P1, P2, P3) = (25, 24, 15)
(W1, W2, W3) = (18, 15, 10)
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X1, X2, X3) (W1. X1) + (W2. X2) + (W3. X3) ≤ M (P1. X1) + (P2. X2) + (P3. X3)
a (1, 2/15, 0)
(18.1) + (15.2/15) + (10.0) ≤ 20 (25.1) + (24.2/15) + (15.0)
20 28,2
20 28,2
b. Pilih
objek dengan bobot terkecil (Wi)
Susun data sesuai kriteria:
(P3, P2, P1) = (15, 24, 25)
(W3, W2, W1) = (10, 15, 18)
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X3, X2, X1) (W3. X3) + (W2. X2) + (W1. X1) ≤ M (P3. X3) + (P2. X2) + (P1. X1)
b (1, 2/3, 0) (10.1) + (15.2/3) + (18.0) ≤ 20 (15.1) + (24.2/3) + (25.0)
20 31
Susun data sesuai kriteria:
(P3, P2, P1) = (15, 24, 25)
(W3, W2, W1) = (10, 15, 18)
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X3, X2, X1) (W3. X3) + (W2. X2) + (W1. X1) ≤ M (P3. X3) + (P2. X2) + (P1. X1)
b (1, 2/3, 0) (10.1) + (15.2/3) + (18.0) ≤ 20 (15.1) + (24.2/3) + (25.0)
20 31
c. Pilih
objek dengan nilai perbandingan profit dengan bobot yang terbesar (Pi/Wi)
Data yang diketahui:
(P1, P2, P3) = (25, 24, 15)
(W1, W2, W3) = (18, 15, 10)
perbandingan profit dengan bobot
P1/ W1 = 25/18 = 1,39
P2/ W2 = 24/15 = 1,6
P3/ W3 = 15/10 = 1,5
Susun data sesuai kriteria:
(P2, P3, P1) = (24, 15, 25)
(W2, W3, W1) = (15, 10, 18)
Data yang diketahui:
(P1, P2, P3) = (25, 24, 15)
(W1, W2, W3) = (18, 15, 10)
perbandingan profit dengan bobot
P1/ W1 = 25/18 = 1,39
P2/ W2 = 24/15 = 1,6
P3/ W3 = 15/10 = 1,5
Susun data sesuai kriteria:
(P2, P3, P1) = (24, 15, 25)
(W2, W3, W1) = (15, 10, 18)
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi
Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X2, X3, X1) (W2. X2) + (W3. X3) + (W1. X1) ≤ M (P2. X2) + (P3. X3) + (P1. X1)
c (1, 1/2, 0) (15.1) + (10.1/2) + (18.0) ≤ 20 (24.1) + (15.1/2) + (25.0)
20 31,5
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X2, X3, X1) (W2. X2) + (W3. X3) + (W1. X1) ≤ M (P2. X2) + (P3. X3) + (P1. X1)
c (1, 1/2, 0) (15.1) + (10.1/2) + (18.0) ≤ 20 (24.1) + (15.1/2) + (25.0)
20 31,5
Dari contoh di atas dapat disimpulkan bahwa fungsi tujuan yang bernilai maximum adalah 31,5 dengan fungsi pembatasnya adalah 20 dan nilai probabilitasnya adalah (X2, X3, X1) = (1, 1/2, 0), jadi disini yang memeberikan hasil optimal pada kriteria yang ke-3 yaitu Pilih objek dengan nilai perbandingan profit dengan bobot yang terbesar (Pi/Wi).
Contoh 2:
persoalan
Knapsack lain dengan 6 objek:
w1 = 100; p1 = 40
w2 = 50; p2 = 35
w3 = 45; p3 = 18
w4 = 20; p4 = 4
w5 =
10; p5 = 10
w6 = 5; p6 = 2
Kapasitas knapsack W = 100
Properti
objek
|
Greedy
by
|
Solusi
Optimal
|
|||||
i
|
wi
|
pi
|
pi /wi
|
profit
|
weight
|
density
|
|
1
|
100
|
40
|
0,4
|
1
|
0
|
0
|
0
|
2
|
50
|
35
|
0,7
|
0
|
0
|
1
|
1
|
3
|
45
|
18
|
0,4
|
0
|
1
|
0
|
1
|
4
|
20
|
4
|
0,2
|
0
|
1
|
1
|
0
|
5
|
10
|
10
|
1,0
|
0
|
1
|
1
|
0
|
6
|
5
|
2
|
0,4
|
0
|
1
|
1
|
1
|
Total
bobot
|
100
|
80
|
85
|
100
|
|||
Total
keuntungan
|
40
|
34
|
51
|
55
|
|||
Pada contoh 2, terlihat algoritma greedy dengan ketiga strategi pemilihan objek tidak berhasil memberikan solusi optimal. Solusi optimal permasalah ini adalah X = (0, 1, 1, 0, 0, 0) dengan total keuntungan = 55.
Dapat di simpulkan Pada soal 2, algoritma greedy dengan strategi pemilihan objek berdasarkan profit memberikan solusi optimal, sedangkan pemilihan objek berdasarkan weight dan density tidak memberikan solusi optimal.
Refrensi : 1. https://kevinkarundeng.wordpress.com/2012/11/05/contoh-soal-algoritma-greedy-dan-knapsack-problem/
3. http://www.diku.dk/hjemmesider/ansatte/pisinger/95-1.pdf
Tidak ada komentar:
Posting Komentar