Scribd
Unggah
7 tayangan7 halaman

Masalah Algoritma Dinamis Terapan

Berdasarkan analisis data yang diberikan, terdapat 3 permasalahan yang dapat diringkas sebagai berikut: 1. Permasalahan knapsack dapat menghasilkan keuntungan maksimum sebesar Rp. 11.700 dengan memilih item Ruby, Sapphire, dan Gold. 2. Jalur terpendek dari node A ke J pada multistage graph adalah A-B-E-H-J. 3. Jalur terpendek untuk mengunjungi 4 kota dan kembali ke Supe ad

Diunggah oleh

Kristianto
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PDF, TXT atau baca online di Scribd
7 tayangan7 halaman

Masalah Algoritma Dinamis Terapan

Berdasarkan analisis data yang diberikan, terdapat 3 permasalahan yang dapat diringkas sebagai berikut: 1. Permasalahan knapsack dapat menghasilkan keuntungan maksimum sebesar Rp. 11.700 dengan memilih item Ruby, Sapphire, dan Gold. 2. Jalur terpendek dari node A ke J pada multistage graph adalah A-B-E-H-J. 3. Jalur terpendek untuk mengunjungi 4 kota dan kembali ke Supe ad

Diunggah oleh

Kristianto
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PDF, TXT atau baca online di Scribd

Tugas Personal ke-2

(Minggu 7 / Sesi 11)

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 19 Kg.

Item Value Weight


Diamond $4,120 3
Zamrud $4,580 4
Ruby $3,720 2
Sapphire $3,860 3
Gold $5,125 6
Pearl $2,250 2
Silver $5,450 8

2. [Multistage Graph] Carilah jalur terpendek dari node A ke node J pada multistage graph
dibawah menggunakan metode dynamic programming (pendekatan forward dan backward)!

1
D G
3 4
7
B 4
5 6
3 3
E H
A J
5 4 2
3
C 8 6 3
F 3 I

3. [Travelling Salesman Problem] Carilah jalur terpendek dari Supe mengunjungi Luhu, Piru,
dan Kairatu dan kembali ke Supe jika diketahui biaya transportasi sebagai berikut
menggunakan metode dynamic programming.

From To Cost

This study source was downloaded by 100000838835617 from [Link] on 09-19-2022 19:28:14 GMT -05:00
COMP6127 - Algorithm Design and Analysis
[Link]
Supe Luhu Rp. 20.000

Supe Piru Rp. 15.000

Supe Kairatu Rp. 25.000

Luhu Supe Rp. 19.000

Luhu Piru Rp. 21.000

Luhu Kairatu Rp. 27.000

Piru Supe Rp. 18.000

Piru Kairatu Rp. 15.000

Piru Luhu Rp. 12.000

Kairatu Piru Rp. 16.000

Kairatu Supe Rp. 26.000

Kairatu Luhu Rp. 17.000

4. [Coin Change Problem] Carilah kombinasi jumlah pecahan uang maksimum yang dapat
dibentuk dari nominal uang 47 dimana pecahan nominal uang adalah 2, 3, dan 7!

This study source was downloaded by 100000838835617 from [Link] on 09-19-2022 19:28:14 GMT -05:00
COMP6127 - Algorithm Design and Analysis
[Link]
Jawaban

1).

No. Item Value Weight v/w Rank


1 Diamond $4,120 3 1373 2
2 Zamrud $4,580 4 1145 4
3 Ruby $3,720 2 1860 1
4 Sapphire $3,860 3 1287 3
5 Gold $5,125 6 854 6
6 Pearl $2,250 2 1125 5
7 Silver $5,450 8 681 7
Mengggunakan rumus ini untuk mengisi tabel

if wt[i] > w then


V[i,w] = V[i-1,w]

else if wt[i] <= w then


V[i,w] = max( V[i-1,w], val[i] + V[i-1, w - wt[i]] )

W=
V 1 2 3 4 5 6 7 8 9 10 11 12 13
0

i=
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0

412 412 412 412 412


1 0 0 0 4120 4120 4120 4120 4120 4120
0 0 0 0 0

412 458 458 412 870


2 0 0 0 8700 8700 8700 8700 8700 8700
0 0 0 0 0

372 412 458 784 784 870 1242 1242 1242 1242 1242
3 0 0 8700
0 0 0 0 0 0 0 0 0 0 0

372 412 458 784 798 870 1242 1256 1256 1256 1256
4 0 0 11700
0 0 0 0 0 0 0 0 0 0 0

372 412 458 784 798 870 1242 1256 1296


5 0 0 11700 … …
0 0 0 0 0 0 0 0 5

372 412 597 784 798 109 1242 1256 1395


6 0 0 11700 … …
0 0 0 0 0 0 0 0 0

372 412 597 784 798 109 1242 1256 1395


7 0 0 11700 … …
0 0 0 0 0 0 0 0 0

This study source was downloaded by 100000838835617 from [Link] on 09-19-2022 19:28:14 GMT -05:00
COMP6127 - Algorithm Design and Analysis
[Link]
14 15 16 17 18 19

0 0 0 0 0 0

4120 4120 4120 4120 4120 4120

8700 8700 8700 8700 8700 8700

1242 1242 1242 1242 1242 1242


0 0 0 0 0 0

1256 1256 1256 1256 1256 1256


0 0 0 0 0 0

… … … … … …

… … … … … …

2140
… … … … …
5

Sehingga didapat gold + zamrud + diamond + ruby + sapphire = 21405 value

Weight = 18

2).

1
D G
3 4
7
B 4
5 6
3 3
E H
A J
5 4 2
3
C 8 6 3
F 3 I
Forward

Cost (4,G) = 7

Cost (4,H) = 3

Cost (4,I) = 3

Cost (3,D) = G+J | H+J = 1+7 | 4+3 = 7 (G,J)

Cost (3,E) = G+J | H+J | I+J = 6+7 | 3+3 | 2+3 = 5 (I,J)

This study source was downloaded by 100000838835617 from [Link] on 09-19-2022 19:28:14 GMT -05:00
COMP6127 - Algorithm Design and Analysis
[Link]
Cost (3,F) = H+J | I+J = 6+3 | 3+3 = 6 (I,J)

Cost (2,B) = B+(3,D) | B+(3,E) | B+(3,F) = 3+7 | 4+5 | 4+6 = 9 (E,I,J)

Cost (2,C) = C+(3,D) | C+(3,F) = 5+7 | 8+6 = 12 (D,G,J)

Cost (1,A) = A+(2,B) | A+(2,C) = 5+9 | 5+12 = 14 (A,E,I,J)

Jadi rute terpendek adalah A,E,I,J

Backward

Cost (2,B) = 5

Cost (2,C) = 3

Cost (3,D) = (A,B)+D | (A,C)+D = 5+3 | 3+5 = 8

Cost (3,E) = (A,B)+E = 5+4 = 9

Cost (3,F) = (A,B)+F | (A,C)+F = 5+4 | 3+8 = 9

Cost (4,G) = (3,D)+G | (3,E)+G = 8+1 | 9+6 = 9

Cost (4,H) = (3,D)+H | (3,E)+H | (3,F)+H = 8+4 | 9+3 | 9+6 = 12

Cost (4,I) = (3,E)+I | (3,F)+I = 9+2 | 9+3 = 11

Cost (5,J) = (4,G)+J | (4,H)+J | (4,I)+J = 9+7 | 12+3 | 11+3 = 14

Jadi rute terpendek adalah A,E,I,J

3).

¿/¿ supe luhu piru kairatu

This study source was downloaded by 100000838835617 from [Link] on 09-19-2022 19:28:14 GMT -05:00
COMP6127 - Algorithm Design and Analysis
[Link]
Supe 20 15 25

Luhu 19 21 27

Piru 18 12 15

Kairatu 16 17 16

C (S,L) = 20

C (S,P) = 15

C (S,K) = 25

C (S,L,K) = 20 + 27 = 47

C (S,L,P) = 20 + 21 = 41

C (S,P,L) = 15 + 12 = 27

C (S,P,K) = 15 + 15 = 30

C (S,K,L) = 25 + 17 = 42

C (S,K,P) = 25 + 16 = 41

C (S,L,K,P) | C (S,K,L,P) = 47 + 16 | 42 + 21 = 63  S = 63 + 18 = 81

C (S,L,P,K) | C (S,P,L,K) = 41 + 15 | 27 + 27 = 54  S = 54 + 16 = 70

C (S,P,K,L) | C (S,K,P,L) = 30 + 17 | 41 + 12 = 47  S = 47 + 19 = 66

Rute terpendek = S,P,K,L,S

This study source was downloaded by 100000838835617 from [Link] on 09-19-2022 19:28:14 GMT -05:00
COMP6127 - Algorithm Design and Analysis
[Link]
Referensi : LN

4).

1
0 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20
0

1 0 1 2 1 1 3 2 1 4 3 2 5 4 3 5 5 4 7 6 6

2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
30 40
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9

9 7 7 11 9 9 1 1 1 15 1 1 1 1 1 1 1 1 2 22
3 2 0 4 3 7 7 5 9 9 8 2

4 4 4 4 4 4 4
1 2 3 4 5 6 7

2 2 2 2 2 2 2
1 5 4 4 8 8 7

Kembalian = 2,3,7

Totalnya 27 kombinasi

This study source was downloaded by 100000838835617 from [Link] on 09-19-2022 19:28:14 GMT -05:00
COMP6127 - Algorithm Design and Analysis
[Link]
Powered by TCPDF ([Link])

Anda mungkin juga menyukai