Suatu ransel mempunyai kapasitas 60 kg, ransel tersebut akan digunakan untuk membawa barang-barang dengan berat masing-masing (W1,,,,,W6)=(10,8,25,12,16,30) dan profitnya (P1,,,,,,,P6)=(25,18,22,13,8,15). Tentukan kombinasi barang-barang yang dapat dimuat,,,, ???
Cara Pengerjaan
Kapasitas = 65kg
Property Objek | Greedy By | Solusi Optimal | |||||
NO | Wi | Pi | Pi/Wi | Weight | Profit | Density | |
1 | 10 | 25 | 2,5 | 1 | 1 | 1 | 1 |
2 | 8 | 18 | 2,25 | 1 | 1 | 1 | 1 |
3 | 25 | 22 | 0,88 | 0 | 1 | 1 | 1 |
4 | 12 | 13 | 1,08 | 1 | 1 | 1 | 1 |
5 | 16 | 8 | 0,5 | 1 | 0 | 0 | 0 |
6 | 30 | 15 | 0,5 | 0 | 0 | 0 | 0 |
Total Bobot | 46 | 55 | 55 | 55 | |||
Total Keuntungan | 64 | 78 | 78 | 78 | |||
Cara diatas tidak menemukan hasil yang maksimal,
Dikarenakan tidak didapat hasil yang maksimal maka dipake cara dibawah ini
ractional KnapsackKarena biasanya Density mengandung hasil maksimal jadi saya ringkas saja cara nya langsung menuju density :
W1X1 + W2X2 +W3X3+W4X4 + W5X5 + W6X6 = 65
10(X1) + 8(X2) + 25(X3) + 12(X4) + 16(X5) + 30(X6) = 65
10(1) + 8(1) + 25 (1) + 12(1) + 16X5 + 30 (0) = 65
(angka X5 tidak mengandung nilai karena berada ditengah-tengah (1/0))
10+8+25+12+16X5+0 = 65
16 X5 = 60-55
16X5 = 10
X5 = 10/16
X5 = 0,63
Sehingga didapat nilai density (1,1,1,1,0,63,0)
Yang kemudian dicari nilai maksimal dengan cara :
Sehingga mempunyai hasil sebagai berikut :
Yang kemudian dicari nilai maksimal dengan cara :
25X1 + 18X2 + 22X3 + 13X4 + 8X5 + 9X6
25(1) + 18(1) + 22(1) + 13(1) + 8(0,63) + 9(0)
25(1) + 18(1) + 22(1) + 13(1) + 8(0,63) + 9(0)
25 + 18 + 22 + 13 + 5,04 + 0 = 83,04
Property Objek | Greedy By | Solusi Optimal | |||||
NO | Wi | Pi | Pi/Wi | Weight | Profit | Density | |
1 | 10 | 25 | 2,5 | 1 | 1 | 1 | 1 |
2 | 8 | 18 | 2,25 | 1 | 1 | 1 | 1 |
3 | 25 | 22 | 0,88 | 0 | 1 | 1 | 1 |
4 | 12 | 13 | 1,08 | 1 | 1 | 1 | 1 |
5 | 16 | 8 | 0,5 | 1 | 0 | 0,63 | 0,63 |
6 | 30 | 15 | 0,5 | 0 | 0 | 0 | 0 |
Total Bobot | 46 | 55 | 65 | 65 | |||
Total Keuntungan | 64 | 78 | 83,4 | 83,4 | |||
Categories:
Logika dan Algoritma