Nama kelompok :
#Tiar Prasetiyo ( 17190782 )
#Rivaldi Nazar Yuniar ( 17190659 )#Tiar Prasetiyo ( 17190782 )
#Eko Mardiyanto ( 17190801 )
#Rian Ferdian Maulana ( 17190684 )
UNIVERSITAS BINA SARANA INFORMATIKA
Kelas ( 17.1E.07 )
LATIHAN SOAL PERTEMUAN 12
LOGIKA DAN ALGORITMA
PERTEMUAN 12 (METODE GREEDY)
1. Diketahui 4 program yang akan disimpan dalam media penyimpanan dengan panjang masing masing 6,8,4,2. Bagaimana proses penyimpanan yang optimal dengan metode greedy?
Jawab :
N = 4 jadi 4 = 4 x 3 x 2 x 1 = 24
Jadi dibutuhkan 24 langkah dalam penyusunannya
L1=6
L2=8
L3=4
L4=2
No
|
Order
|
D(L)
|
Total
|
1
|
1,2,3,4
|
6+(6+8)+(6+8+4)+(6+8+4+2)
|
58
|
2
|
1,2,4,3
|
6+(6+8)+(6+8+2)+(6+8+2+4)
|
56
|
3
|
1,3,2,4
|
6+(6+4)+(6+4+8)+(6+4+8+2)
|
54
|
4
|
1,3,4,2
|
6+(6+4)+(6+4+2)+(6+4+2+8)
|
50
|
5
|
1,4,2,3
|
6+(6+2)+(6+2+8)+(6+2+8+4)
|
46
|
6
|
1,4,3,2
|
6+(6+2)+(6+2+4)+(6+2+4+8)
|
40
|
7
|
2,1,4,3
|
8+(8+6)+(8+6+2)+(8+6+2+4)
|
64
|
8
|
2,1,3,4
|
8+(8+6)+(8+6+4)+(8+6+4+2)
|
60
|
9
|
2,3,1,4
|
8+(8+4)+(8+4+6)+(8+4+2+6)
|
58
|
10
|
2,3,4,1
|
8+(8+4)+(8+4+2)+(8+6+6+2)
|
54
|
11
|
2,4,3,1
|
8+(8+2)+(8+2+4)+(8+2+6+4)
|
52
|
12
|
2,4,1,3
|
8+(8+2)+(8+2+6)+(8+2+4+6)
|
58
|
13
|
3,4,2,1
|
4+(4+2)+(4+2+8)+(4+2+8+6)
|
44
|
14
|
3,4,1,2
|
4+(4+2)+(4+2+6)+(4+2+6+8)
|
42
|
15
|
3,2,1,4
|
4+(4+8)+(4+8+6)+(8+4+6+2)
|
54
|
16
|
3,2,4,1
|
4+(4+8)+(4+8+2)+(8+4+2+6)
|
50
|
17
|
3,1,2,4
|
4+(4+6)+(4+6+8)+(4+6+8+2)
|
40
|
18
|
3,1,4,2
|
4+(4+6)+(4+6+2)+(4+6+2+8)
|
46
|
19
|
4,3,2,1
|
2+(2+4)+(2+4+8)+(2+4+8+6)
|
42
|
20
|
4,3,1,2
|
2+(2+4)+(2+4+6)+(2+4+6+8)
|
40
|
21
|
4,2,1,3
|
2+(2+8)+(2+8+6)+(2+8+6+4)
|
48
|
22
|
4,2,3,1
|
2+(2+8)+(2+8+4)+(2+8+4+6)
|
46
|
23
|
4,1,2,3
|
2+(2+6)+(2+6+8)+(2+6+8+4)
|
46
|
24
|
4,1,3,2
|
2+(2+6)+(2+6+4)+(2+6+4+8)
|
42
|
4 Dari nilai diatas didapat nilai minimal adalah
a. Nilai terkecil pertama adalah 40, yaitu untuk posisi penyimpanan urutan ke-1 pada posisi ke-6
b b. Nilai terkecil pertama adalah 42, yaitu untuk posisi penyimpanan urutan ke-3 pada posisi ke-2
c. Nilai terkecil pertama adalah 46, yaitu untuk posisi penyimpanan urutan ke-4 pada posisi ke-4
d. Nilai terkecil pertama adalah 52, yaitu untuk posisi penyimpanan urutan ke-2 pada posisi ke-5
2. Diketahui 4 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal sebesar 30kg. Berat masing masing adalah 15kg, 10kg, 18kg, dan 20kg dimana setiap barang memiliki profit sebesar masing masing 20, 25, 9 dan 15. Tentukan barang mana saja yang dapat disimpan dalam tempat penyimpanan sehingga diperoleh nilai profit yang maksimal! (Cari dengan kriteria greedy dan algoritma greedy).
1. Diketahui
N = 4
M = 30 Kg
W1 = 15 | P1 = 20
W2 = 10 | P2 = 25
W3 = 18 | P3 = 9
W4 = 20 | P4 = 15
2. Mengurutkan Berdasarkan Profit Terbesar (Pi)
P2 = 25 | W2 = 10
P1 = 20 | W1 = 15
P4 = 15 | W4 = 20
P3 = 9 | W3 = 18
a. Nilai terkecil pertama adalah 40, yaitu untuk posisi penyimpanan urutan ke-1 pada posisi ke-6
b b. Nilai terkecil pertama adalah 42, yaitu untuk posisi penyimpanan urutan ke-3 pada posisi ke-2
c. Nilai terkecil pertama adalah 46, yaitu untuk posisi penyimpanan urutan ke-4 pada posisi ke-4
d. Nilai terkecil pertama adalah 52, yaitu untuk posisi penyimpanan urutan ke-2 pada posisi ke-5
2. Diketahui 4 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal sebesar 30kg. Berat masing masing adalah 15kg, 10kg, 18kg, dan 20kg dimana setiap barang memiliki profit sebesar masing masing 20, 25, 9 dan 15. Tentukan barang mana saja yang dapat disimpan dalam tempat penyimpanan sehingga diperoleh nilai profit yang maksimal! (Cari dengan kriteria greedy dan algoritma greedy).
1. Diketahui
N = 4
M = 30 Kg
W1 = 15 | P1 = 20
W2 = 10 | P2 = 25
W3 = 18 | P3 = 9
W4 = 20 | P4 = 15
2. Mengurutkan Berdasarkan Profit Terbesar (Pi)
P2 = 25 | W2 = 10
P1 = 20 | W1 = 15
P4 = 15 | W4 = 20
P3 = 9 | W3 = 18
· P2 = 25 | W2 = 10
· P1 = 20 | W1 = 15
· P3 = 9 | W3 = 18
· P4 = 15 | W4 = 20
4. Perbandingan Profit dengan Bobot
· P1 = 20 | W1 = 15
· P2 = 25 | W2 = 10
· P3 = 9 | W3 = 18
· P4 = 15 | W4 = 20
Perbandingan Proft dengan Bobot
· P1/W1 = 20/15 = 1.3 <<< Urutan Kedua >>>
· P2/W2 = 25/10 = 2.5 <<< Urutan Pertama >>>
· P3/W3 = 9/18 = 0.5 <<< Urutan Ke Empat >>>
· P4/W4 = 15/20 = 0.75 <<< Urutan Ketiga >>>
Tidak ada komentar:
Posting Komentar