Soal Bonus : Knapsack Problem

Knapsack problem adalah 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).

Contoh Soal :

KNAPSACK PROBLEM DALAM METODE GREEDY
Diketahui bahwa kapasitas M = 30 kg ,
Dengan jumlah barang n=3

Berat Wi masing-masing barang

(W₁, W₂, W₃) = (28, 25, 20)         
Nilai Pi masing-masing barang
(P₁, P₂, P₃) = (38, 34, 25)
Pilih barang dengan Nilai Profit Maksimal
P1 = …  –> X1 = …
P2 = …  –> X2 =  …
P3 = … –> X3 = …
Pilih barang dengan Berat Minimal
W1 = …  –> X1 = …
W2 = …  –> X2 = …
W3 = …  –>X3 = …
Pilih barang dengan menghitung perbandingan yang terbesar dari Profit dibagi Berat (Pi/Wi) yang diurut secara tidak naik, yaitu :
P1/W1 = … = … –> X1 = …
P2/W2 = … = …  –> X2 = …
P3/W3 = … = …  –> X3 = …

Fungsi Pembatas dicari dengan rumus:  

Tabel berdasarkan elemen dari ke-3 kriteria metode Greedy yaitu:

Nilai profit maksimal = ….

Penyelesaian  :
Pilih barang dengan Nilai Profit Maksimal
P1 = 38 à X1 = 1, dimisalkan sebagai batas atas nilai
P2 = 34 à X2 = 2/15, dihitung dengan Fungsi Pembatas
P3 = 25 à X3 = 0, dimisalkan sebagai batas bawah nilai

Menyelesaikan fungsi pembatas : 

Pilih barang dengan Berat Minimal
W1 = 28 à X1 = 0, sebagai batas bawah
W2 = 25 à X2 = 2/5,dihitung dgn Fungsi Pembatas
W3 = 20 à X3 = 1, sebagai batas atas

Menyelesaikan fungsi pembatas :

Pilih barang dgn menghitung perbandingan yg terbesar dari Profit dibagi Berat (Pi/Wi) yg diurut secara tidak naik, yaitu :
P1/W1 = 38/28 à = 1,35 karena terkecil maka X1 = 5/28 
P2/W2 = 34/25 à = 1,36 karena terbesar maka X2 =  1
P3/W3 = 25/20 à = 1,25 dengan Fungsi pembatas X3 = 0

Menyelesaikan fungsi pembatas :

Tabel berdasarkan elemen dari
ke-3 kriteria metode Greedy yaitu :

Nilai profit maksimal adalah 40.8  à diambil dari nilai terbesar.
Dengan cara :

Refernsi:
http://slideplayer.info/slide/3716032/
https://hendryprihandono.wordpress.com/
https://en.wikipedia.org/