6 0 208 KB
Tugas Personal ke-2 (Minggu 7 / Sesi 11)
Hamid Machfudin Sukardi
2401973053 / TXCA
1. [Knapsack Problem] Berikut ini merupakan permasalahan Knapsack tentukan kombinasi barang yang dapat diambil yang mampu memberikan keuntungan maksimum dengan menggunakan konsep metode Dynamic Programming apabila diketahui barang terbatas dan tak dapat dipecah dimana kapasitas maksimum dari tas adalah 27 Kg. Barang A B C D E F G
Nilai (Rp) 15 Juta 28 Juta 14 Juta 40 Juta 50 Juta 30 Juta 75 Juta
Berat (Kg) 4 3 2 5 10 5 7
Jawab : Tabel Dynamic Programing
Jadi Keuntungan Maksimal dari persoalan Knapsack diatas adalah 202 Juta dengan kombinasi A–B–C–D–F–G
COMP6742- Algorithm Design and Analysis
2. [Multistage Graph] Carilah jalur terpendek dari node A ke node L pada multistage graph dibawah menggunakan metode dynamic programming (backward)!
Jawab : ASAL
SOLUSI OPTIMUM Bobot (Asal)
V5
I
9
L
J
8
L
K
7
L
ASAL
SOLUSI OPTIMUM I
J
F
22
G
21
H
B. ASAL
V4
25
22
I
24
21
I
22
J&K
22
ASAL
K
22 SOLUSI OPTIMUM
F
G
H
B. ASAL
V3
B
44
45
43
43
H
C
50
48
48
G
D E
47 47
46
COMP674247 Algorithm H Design and Analysis 46
H
ASAL
A
SOLUSI OPTIMUM B
C
D
E
B. ASAL
V2
60
67
65
66
60
B
Jadi jalur terpendek dari node A ke L jika menggunkan Dynamic Programing adalah 61 dengan bentuk :
COMP6742- Algorithm Design and Analysis
3. [Travelling Salesman Problem] Carilah jalur terpendek dengan metode dynamic programming, dari kota A mengunjungi kota B, C, dan D dan kembali ke A jika diketahui jarak antar kota seperti table berikut Dari kota A A B B C C C D D
Ke kota B C A D A B D A C
Jarak (km) 6 2 5 5 4 3 3 4 7
Jawab :
COMP6742- Algorithm Design and Analysis
Mencari Jalur Terpendek A mengunjungi kota B, C, dan D dan kembali ke A
P (B,D) = 5 P (C,A) = 2 P ({BD},{CA}) = 5 + 7 + 4 = 16 P (A,{BDCA}) = 22 P ({B,D},A) = 9 P (C, {BDA)= 12 P(A,{CBDA}) = 14 Jadi jarak minimum dari A mengunjungi kota B, C, dan D dan kembali ke A adalah 14 km dengan rute ACBDA
COMP6742- Algorithm Design and Analysis
4. [Coin Change Problem] Dengan menggunakan metode dynamic programming carilah kombinasi jumlah uang pecahan minimum yang dapat dibentuk dari nominal uang 284 dengan menggunakan pecahan uang dengan nominal 1, 5, 10, 25, 50 dan 100! Jawab : Nominal Uang = 284 Nominal Pecahan Uang = 1, 5, 10, 25, 50, 100 Dynamic Programing : f(284) = 284 - 100 = 184 =184 – 100 = 84, dengan ini maksimal pecahan 100 adalah 2 kali f(84)
= 84 – 50 = 34, dengan ini maksimal pecahan 50 adalah 1 kali
f(34)
= 34 – 25 = 9, dengan ini maksimal pecahan 25 adalah 1 kali
f(9)
= 9 – 5 = 4, dengan ini maksimal pecahan 5 adalah 1 kali
f(4)
= 4 -1 = 3 =3–1=2 =2–1=1 = 1 – 1 = 0, dengan ini maksimal pecahan 1 adalah 4 kali
Jadi Kombinasi yang diambil adalah 2 kali Pecahan 100, 1 kali Pecahan 50, 1 kali Pecahan 25, 1 kali Pecahan 5, dan 4 kali Pecahan 1.
COMP6742- Algorithm Design and Analysis