Herlawati

Tugas UAS Logika Algoritma-Knapsack Problem-Metode Greedy

Posted on Desember 22, 2013

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 = ….