TP2-W7-S11-R1 Jawaban [PDF]

Citation preview

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