LAPORAN ANALISIS ALGORITMA
“DYNAMIC PROGRAMMING” Laporan Ini Disusun Sebagai Tugas Pengganti Kuis Pada Mata Kuliah Analisis Algoritma
Disusun Oleh : Agung Eka Lukmantara (10113319) Analgo - 4
Dosen : Angga Setiyadi, S.Kom
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK dan ILMU KOMPUTER UNIVERSITAS KOMPUTER INDONESIA BANDUNG, Januari 2015
KATA PENGANTAR Puji syukur kami panjatkan kepada Allah SWT. Yang telah melimpahkan rahmat dan hidayah-Nya, serta dengan do’a restu kedua orang tua, sehingga penulis dapat menyelesaikan laporan ini. Laporan ini merupakan salah satu tugas pada mata kuliah “Analisis Algoritma” tahun ajaran 2014 / 2015. Penulis sadar bahwa laporan ini masih sangar kurang dari apa yang diharapkan, namun penulis berharap mudah-mudahan hasil laporan ini dapat dimanfaatkan bagi semua pihak, dan untuk kesempurnaan laporan ini bersedia untuk menerima kritikan dan saran.
Bandung, Januari 2015
Penulis
DAFTAR ISI KATA PENGANTAR.....................................................................................................2 DAFTAR ISI ..................................................................................................................3 BAB I .............................................................................................................................4 1.1.
Latar Belakang Masalah.......................................................................................4
1.2.
Maksud dan Tujuan .............................................................................................4
1.3.
Batasan Masalah ..................................................................................................5
BAB II ............................................................................................................................6 2.1.
Definisi Strategi Dynamic Programming .............................................................6
2.2.
Kekurangan dan Kelebihan Strategi Dynamic Programming .............................. 10
2.2.1.
Kelebihan Dynamic Programming ................................................................ 10
2.2.2.
Kekurangan Dynamic Programming ............................................................. 10
2.3.
Multistage Graph Problem (Permasalah Mencari Lintasan Terpendek) ............. 11
2.4.
Study Kasus Dynamic Programming ................................................................. 13
2.4.1.
Knapsack Problem (Pendekatan Dynamic Programming).............................. 13
2.4.2.
Coin Cange Problem ..................................................................................... 16
2.4.3.
Traveling Salesman Problem ......................................................................... 16
BAB III ......................................................................................................................... 19 3.1.
Algoritma .......................................................................................................... 19
3.1.1.
Algoritma Knapsack Problem ........................................................................ 19
3.1.2.
Algoritma Coin Change Problem .................................................................. 21
3.1.3.
Algoritma Traveling Salesman Problem ......................................................... 22
3.2.
Program............................................................................................................. 24
1.1.1.
Program Knapsack Problem ........................................................................... 24
1.1.2.
Program coin Change Problem ...................................................................... 26
1.1.3.
Program Traveling Salesman Problem ........................................................... 27
BAB IV ........................................................................................................................ 29 4.1.
Kesimpulan ....................................................................................................... 29
4.2.
Saran ................................................................................................................. 29
DAFTAR PUSTAKA ................................................................................................... 31
BAB I PENDAHULUAN 1.1. Latar Belakang Masalah Untuk menyelesaikan suatu masalah tentunya membutuhkan suatu cara atau solusi agar masalah tersebut terselesaikan dengan baik. Setiap masalah apapun tentunya
membutuhkan yang namanya solusi atau cara. Dalam sebuah
penelitianpun diperlukan solusi untuk membantu memecahkan suatu masalah. Sama
halnya
dengan laporan ini
yang
membahas tentang
“Dynamic
Programming”. Dynamic Programming mirip seperti metode divide-and-conquer yang menyelesaikan
suatu
problem
dengan
mengkobinasikan
solusi
menjadi
subproblem. Divide-and-conquer membagi problem menjadi subproblem yang independen.
Kemudian
menyelesaikan
subproblem
secara
rekursif
dan
mengkombinasikan solusi tersebut untuk menyelesaikan problem utama. Sedangkan dynamic programming cocok digunakan ketika subproblem tidak indepen-den, jadi ketika subproblem terbagi menjadi sub-subproblem.
1.2. Maksud dan Tujuan Maksud dari
program dinamis adalah suatu teknik matematis yang
biasanya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Dalam hal ini program dinamis menyediakan prosedur sistematis untuk menentukan kombinasi keputusan yang optimal.
Tujuan utama model ini ialah untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu. Tidak seperti pemrograman linier, tidak ada bentuk matematis standar untuk perumusan pemrograman dinamis. Akan tetapi, pemrograman dinamis adalah pendekatan umum untuk pemecahan masalah dan persamaan tertentu yang digunakan di dalamnya harus dibentuk sesuai dengan situasi masalah yang dihadapi.
1.3. Batasan Masalah Terdapat beberapa poin dalam batasan masalah laporan ini, yaitu : 1.
Memecah
permasalahan
asli
(original
problem)
menjadi
bagian
permasalahan (subproblem) yang juga disebut sebagai tahapan (stage), dengan aturan keputusan di tiap-tiap tahapan. 2.
Memecahkan tahapan terakhir dari permasalahan dengan semua kondisi dan keadaan yang memungkinkan.
3.
Bekerja mundur dari tahap terakhir, dan memecahkan tiap tahap. Hal ini dikerjakan dengan mencari keputusan optimal dari tahap tersebut sampai dengan tahap terakhir.
4.
Solusi optimal dari permasalhan didapatkan jika semua tahap sudah terpecahkan.
BAB II DYNAMIC PROGRAMMING
2.1. Definisi Strategi Dynamic Programming Dynamic programming dapat didefinisikan sebagai suatu pendekatan matematik yang memiliki prosedure sistematis yang dirancang sedemikian rupa dengan tujuan untuk mengoptimalkan penyelesaian suatu masalah tertentu yang diuraikan menjadi sub-sub masalah yang lebih kecil yang terkait satu sama lain dengan tetap memperhatikan kondisi dan batasan permasalahan tersebut. Struktur dynamic programming untuk dapat dimengerti secara lebih jelas dan lebih spesifik, umumnya dideskripsikan dengan suatu sistem notasi. Struktur dynamic programming disebut juga dengan model dynamic programming. Notasi dan simbol yan digunakan dalam model dynamic programming adalah beragam, namun secara umum dapat dinyatakan sebagai berikut : i
= Tahap keputusan ke - i.
n
= Banyak tahap keputusan.
Xi
= Variable keputusan pada tahap keputusan ke – i.
Si(Si – 1, Xi) = Status pada tahap keputusan ke – i. ri(Si,Xi)
= Return pada tahap keputusan ke – i.
fi(Si,Xi)
= Nilai keputusan pada tahap keputusan ke – i, untuk status Si dan variable keputusan Xi.
fi*(Si)
= Nilai keputusan optimal pada tahap keputusan ke – i, untuk status Si.
X1 S0
Stage 1
X2 S1
r1(S1,X1) f1(S1,X1)
Stage 2
Xi S2
r2(S2,X2) f2(S2,X2)
Stage i
Si-1
Xn-1 Si
ri(Si,Xi) fi(Si,Xi)
Sn-2
Stage n-1
Xi Sn-1
rn-1(Sn-1,Xn-1) fn-1(Sn-1,Xn-1)
Stage n
Sn
rn(Sn,Xn) fn(Sn,Xn)
* Struktur dan Sistem Notasi Dynamic Programming
Dynamic Programming (biasa disingkat DP) adalah suatu teknik algoritma untuk memecahkan masalah dimana solusi optimal dari masalah tersebut dapat dipandang sebagai suatu deret keputusan. Pada umumnya dynamic programming digunakan untuk masalah optimisasi. Dimana suatu permasalahan memiliki banyak solusi. Setiap solusi memiliki nilai masing-masing. Dan ingin ditemukan solusi dengan nilai yang optimum (maksimal atau mininal). Dynamic programming dapat dibagi menjadi empat tahap yang berurutan sebagai berikut : 1. Karakterisasi struktur pada solusi optimasi 2. Mendefinisikan nilai solusi optimal secara rekursif 3. Menghitung nilai solusi optimal pada model bottom-up 4. Menyusun solusi optimal dari informasi hasil perhitungan Langkah 1 sampai langkah 3 adalah dasar dynamic-programming dalam menemukan solusi untuk suatu problem, langkah ke-4 dapat dilakukan jika nilai solusinya optimal diperlukan.
Dynamic programming sebagai suatu pendekatan matematik memiliki beberapa prinsip dasar yang terkait erat satu sama lain. Prinsip-prinsip dasar tersebut, yaitu : Prinsip pertama dalam model Dynamic programming adalah bahwa masalah dapat dibagi menjadi bagian-bagian masalah yang lebih kecil. Masalah yang lebih kecil atau sub masalah ini tersebut sebagai tahap keputusan (stage). Setiap masalah uang akan diselesaikan, terlebih dahulu dibagi-bagi menjadi beberapa masalah kecil dengan maksud memudahkan evaluasi masalah untuk mendapatkan keputusan optimal dari tiap-tiap tahap yang pada akhirnya akan menghasilkan satu keputusan yang optimal. Oleh karena itu model Dynamic programming disebut juga model multi stage programming (model multi tahap). Proses urutan pembagian masalah dalam model Dynamic programming ditunjukan pada gambar berikut :
Tahap 3
Tahap 2
Tahap 1
**Proses Urutan pembagian masalah Secara Mundur Prinsip kedua dalam model Dynamic programming adalah tentang status (state). Pengertian status (state) dalam Dynamic programming adalah arus informasi dari suatu tahap ke tahap berikutnya. Arus informasi yang masuk ke suatu tahap disebut status input, sedangkan arus informasi yang keluar dari suatu tahap diseebut stats output. Status input penting, karena keputusan pada tahap berikutnya tergantung dari status input sebelumnya. Jadi, status input untuk tahap keputusan n-1 merupakan status output dari tahap keputusan sebelumnya, yaitu
tahap keputusan n. Sedangkan status output dari tahao keputusan n akan menjadi status input untuk tahap kepututsan berikutnya, yaitu tahap keputusan n-1. Status Input Tahap 3
Status Input Tahap 2 Tahap Keputusan 3
Status Input Tahap 1 Tahap Keputusan 2
Status output Tahap 3
Tahap Keputusan 1 Status output Tahap 2
***Hubungan Status Input Dengan Tahap Keputusan
Prinsip ketiga dalam model Dynamic Programming adalah tentang variabel
keputusan.
Variabel
keputusan
dalam
Dynamic
Programming
dainyatakan dalam berbagai bentuk keputusan alternatif yang dapat dipilih pada saat pengambilan keputusan pada tahap tertentu. Berbagai alternatif keputusan yang dapat diambil dalam setiap tahap keputusan dapat dibatasi dengan sejumlah persyaratan yang dikenalkan dalam struktur masalah. Prinsip keempat dalam model Dynamic Programming
adalah tentang
fungsi transformasi. Fungsi transformasi memberikan penjelasan tentang bagaimana hubungan antara tahap keputusan yang satu dengan tahap keputusan yang lain dalam Dynamic Programming transformasi juga menyatakan tentang
diformulasikan. Selain itu fingsi
hubungan fungsional nilai status pada
setiaptahap keputusan. Hubngan status dalam tahap keputusan yang berurutan bersifat berulang, artinya jika terdapat tahap keputusan n dalam hubungannya dengan thap keputusan n-1 maka perhitungan untuk nilai status n-1 menggunakan nilai status n dari keputusan pada tahap n.
2.2. Kekurangan dan Kelebihan Strategi Dynamic Programming 2.2.1. Kelebihan Dynamic Programming Terdapat beberapa kelebihan pada Dynamic Programming, diantaranya :
Proses pemecahan suatu masalah yang kompleks menjadi sub-sub masalah yang lebih kecil membuat sumber permasalahan dalam rangkaian proses masalah tersebut menjadi lebih jelas untuk diketahui.
Pendekatan Dynamic Programming dapat diaplikasikan untuk berbagai macam masalah pemrograman matematik, karena Dynamic Programming cenderung lebih fleksibel dari pada teknik optimasi lain.
Prosedure perhitungan Dynamic Programming juga memperkenankan bentuk analisis sensitivitasi terdapat pada setiap variabel status (state) maupun pada variabel yang ada di masing-masing tahap keputusan (stage).
Dynamic Programming dapat menyesuaikan sistematik perhitungannya menurut ukuran masalah yang tidak selalu tetap dengan melakukan perhitungan satu per satu secara lengkap dan menyeluruh.
2.2.2. Kekurangan Dynamic Programming Disamping memiliki kelebihan, Dynamic Programming
juga memiliki
beberapa kekurangan, diantaranya :
Penggunaan Dynamic Programming jjika tidak dilakukan secara tepat, akan mengakibatkan ketidakefisienan biata maupun waktu. Karena dalam menggunakan Dynamic Programming diperlukan keahlian, pengetahuan, dan seni untuk merumuskan suatu masalah yang kompleks, terutama yang
berkaitan dengan penetapan fungsi transformasi dari permasalahan tersebut.
Dynamic Programming tidak memiliki suatu bentuk formulasi matematik yang baku untuk digunakan secara konsekuen, sehingga perhitungan untuk menghasilkan keputusan optimal yang dilakukan terbatas pada kondisi tertentu.
Hambatan terbesar pada Dynamic Programming adalah masalah dimensionalitas, yaitu masalah dimana peningkatan variabel keadaan yang digunakan dalam perhitungan pemrograman dinamis akan menambah beban memory komputer serta menambah lama waktu perhiutngan.
2.3. Multistage Graph Problem (Permasalah Mencari Lintasan Terpendek) Permasalahan pencarian rute terpendek merupakan suatu masalah yang sangat terkenal di dunia Informatika. Dari dahulu hingga sekarang telah dikembangkan
berbagai algoritma untuk memecahkan permasalahan ini.
Penentuan rute terpendek dari satu titik ke titik yang lain adalah masalah yang sering ditemui dalam kehidupan sehari-hari. Berbagai kalangan menemui permasalahan serupa dengan variasi yang berbeda, contohnya seorang pengemudi yang mencari jalur terpendek dari tempat asal ke tempat tujuan, pengantar pesanan makanan cepat saji yang juga mencari jalur terpendek dari tempat asal ke tempat tujuan, dan juga seorang desainer jaringan komputer yang harus mendesain skema perutean pada jaringan yang dia
tangani agar memaksimalkan performa jaringan dan meminimalkan beban yang harus ditangani oleh jaringan tersebut. Persoalan untuk menentukan rute terpendek pada graph multitahap (multistage graph) dan algoritma efisien yang tersedia untuk menghitung rute terpendek. Rute terpendek yang diperoleh akan meminimumkan fungsi linier lintasan jarak dan waktu. Perumusan persoalan ini akan menjadi salah satu kegunaan dari rute jarak terpendek. Algoritma yang digunakan untuk menentukan rute terpendek pada graph multitahap (multistage graph) adalah Dynamic Programming. Seiring dengan waktu yang berjalan dan juga perkembangan ilmu pengetahuan dan teknologi permasalahan pencarian rute terpendek ini telah terpecahkan dengan berbagai algoritma salah satunya dengan algoritma Dynamic Programming. Algoritma yang digunakan untuk menentukan rute terpendek pada graph multitahap (multistage graph) adalah Dynamic Programming. Algoritma Dynamic Programming adalah suatu metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Pada Algoritma Dynamic Programming rangkaian keputusan
yang
optimal dibuat dengan menggunakan prinsip
optimalitas. Prinsip optimalitas yaitu jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal. Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal.
2.4. Study Kasus Dynamic Programming 2.4.1. Knapsack Problem (Pendekatan Dynamic Programming) Knapsack adalah tas atau karung. Karung digunakan untuk memuat sesuatu. Dan
tentunya tidak semua objek dapat ditampung di dalam karung
tersebut, hanya menampung barang yang pentingnya saja. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran kapasitas karung. Setiap objek itupun tidak harus kita masukkan seluruhnya. Tetapi bisa juga sebagian saja. Knapsack problem memiliki tiga jenis solusi, yaitu:
Solusi Knapsack 0/1 (Zero One) Sesuatu yang dimasukkan kedalam karung dimensinya harus dimasukkan semua atau tidak sama sekali atau setiap barang hanya tersedia satu unit.
Solusi Knapsack Bounded Sesuatu yang dimasukkan kedalam karung dimensinya bisa dimasukkan sebagaian atau seluruhnya.
Solusi Knapsack Unbounded Setiap barang tersedia lebih dari satu unit dan juga jumlahnya tak terbatas.
Knapsack problem bisa diselesaikan dengan berbagai cara. Ada beberapa strategi algoritma yang bisa menghasilkan solusi optimal, diantaranya adalah Brute Force. Tapi strategi ini tidak efisien, jadi knapsack problem pada laporan ini akan diselesaikan dengan Greedy Algorithm yaitu solusi yang mencari nilai optimum. Algoritma ini memecahkan permasalahan langkah per langkah, pada setiap langkah:
Mengambil pilihan terbaik yang bisa diperoleh saat itu juga tanpa memperatikan konsekuensi kedepan (prinsip “take what you can get now!”).
Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.
Contoh Permasalah :
Jumlah barang yang dapat diambil n=3 Kapasitas maksimum karung M=5
f1(y)
Barang-i 1 2 3 M=5
= max{f0(y), p1 + f0(y – w1)} = max{f0(y), 65 + f0(y – 2)}
wi 2 3 1
Solusi Optimum Y
f0(y)
65 + f0(y – 2)
f1(y)
(x1*, x2*, x3*)
0
0
-
0
(0, 0, 0)
1
0
-
0
(0, 0, 0)
2
0
65
65
(1, 0, 0)
3
0
65
65
(1, 0, 0)
4
0
65
65
(1, 0, 0)
5
0
65
65
(1, 0, 0)
pi 65 80 30
f2(y)
= max{f1(y), p2 + f1(y – w2)} = max{f1(y), 80 + f1(y – 3)}
Solusi Optimum Y
f1(y)
0
0
1
f2(y)
(x1*, x2*, x3*)
80 + (-) = -
0
(0, 0, 0)
0
80 + (-) = -
0
(0, 0, 0)
2
65
80 + (-) = -
65
(1, 0, 0)
3
65
80 + 0 = 80
80
(0, 1, 0)
4
65
80 + 0 = 80
80
(0, 1, 0)
5
65
80 + 65 = 145
145
(1, 1, 0)
f3(y)
80 + f1(y – 3)
= max{f2(y), p3 + f2(y – w3)} = max{f2(y), 30 + f2(y – 1)}
Solusi Optimum f3(y)
(x1*, x2*, x3*)
30 + (-) = -
0
(0, 0, 0)
0
30 + (-) = -
0
(0, 0, 0)
2
65
30 + 0 = 30
65
(1, 0, 0)
3
80
30 + 65 = 95
95
(1, 0, 1)
4
80
30 + 80 = 110
110
(0, 1, 1)
5
145
30 + 80 = 110
145
(1, 1, 0)
Y
f2(y)
0
0
1
30 + f2(y – 1)
Solusi optimum X = (1, 1, 0) dengan p = f = 145.
2.4.2. Coin Cange Problem Coin change problem adalah proses di mana menukarkan kepala coin yang muncul dengan tailnya, atau kasus yang lebih mudahnya adalah kasus penukaran mata uang rupiah ke dollar , dimana jumlah nominal dalam rupiah akan di kalikan dengan angka(dollar) yang user ingin kan. Dengan adanya program dynamic programming ini pengguna dapat menyelesaikan suatu permasalahnya dengan mudah.
2.4.3. Traveling Salesman Problem TSP atau Traveling Salesman Problem adalah salah satu masalah distribusi yang cukup lama dibahas dalam kajian optimasi. Masalahnya adalah bagaimana seorang salesman mengunjungi seluruh kota di suatu daerah dan kembali ke kota awal keberangkatan dengan aturan bahwa tidak boleh ada kota yang dikunjungi lebih dari satu kali. Berikut
adalah
aturan-aturan
yang
mengidentifikasikan
bahwa
permasalahan tersebut adalah TSP: 1. Perjalanan dimulai dan diakhiri di kota yang sama sebagai kota asal sales. 2. Seluruh kota harus dikunjungi tanpa satupun kota yang terlewatkan. 3. Salesman tidak boleh kembali ke kota asal sebelum seluruh kota terkunjungi. 4. Tujuan penyelesaian permasalahan ini adalah mencari nilai optimum dengan meminimumkan jarak total rute yang dikunjungi dengan mengatur urutan kota.
Perhatikan contoh berikut: Seorang salesman akan mengawali perjalanannya di kota asal (Kota A) untuk mengunjungi seluruh kota yaitu kota A sampai kota F. Perhatikan gambar berikut.
Dari study kasus tersebut didapatkan salah satu kemungkinan jalur yang paling optimum dengan jalur urutan kota di mulai dari kota A, di lanjutkan menuju ke kota E, dilanjutkan menuju ke kota F, dilanjutkan menuju ke kota C, dilanjutkan menuju ke kota D, dilanjutkan kembali menuju ke kota B, lalu yang terakhir kembali ke kota A. Tentunya hasil tersebut dengan mempertimbangkan jarak dari masing-masing kota hingga menghasilkan kombinasi urutan kota dengan jarak yang optimum. Perhatikan gambar dibawah ini.
BAB III ALGORITMA DAN PROGRAM 3.1. Algoritma 3.1.1. Algoritma Knapsack Problem Procedure knapsack::input(Output n,c:integer; Input i:integer) Deklarasi : Algoritma : Output<<" Knapsack dengan Dynamic programming"; Output<<" Berapabanyak item yang andaperlukan : "; Input>>n; Output<<"masukkan kapasitas "; Input>>c; Output<<"masukkan "<
>w[i]; Output<<"\nmasukkan profit/value"<>v[i]; endfor endprocedure Procedure knapsack::knap(Input i,n,c,j,d,w:integer) Kamus : Algoritma : For i:= 0 to n do d[i][0]=0; For j:= 1 to c do d[0][j]=0; For(i=1;i<=n;i++) { For(j=1;j<=c;j++) { if((j-w[i])<0) then d[i][j]=d[i-1][j]; else d[i][j]=max(d[i-1][j],v[i]+(d[i-1][j-w[i]])); endif endfor endfor endprocedure Procedure knapsack::output(Input n,i,j,d,c:integer) Deklarasi :
Algoritma : Output<<"Nilaiperhitungantertinggiuntuk "<< n <<" items:"<<endl; For(i=0;i<=n;i++) For(j=0;j<=c;j++) Output<b) then return a; else return b; endfunction {Algoritma Utama} Deklarasi : class knapsack { w[20],v[20],d[10][10],n,c,i,j: integer; public: Procedure input(Output n,c:integer; Input i:integer ); Procedure knap(Input i,n,c,j,d,w:integer); Function knapsack::max(a :integer,b :integer ) → integer Procedure output(Input n,i,j,d,c:integer); }; Algortima : knapsack k; k.input(Output n,c:integer; Input i:integer ); k.knap(Input i,n,c,j,d,w:integer); k.output(Input n,i,j,d,c:integer);
3.1.2. Algoritma Coin Change Problem
Function CoinChangeDynamic(input jumlah, d[], size, C[], s[] : Integer) →integer C[0] = 0; For(int j = 1; j <= jumlah; j++) { C[j] = INT_MAX; For(int i = 0; i < size; i++) { if(j >= d[i] and 1 + C[j-d[i]] < C[j] ) then C[j] = 1 + C[j-d[i]]; // i-th denomination used For the amount of j s[j] = i; endif endfor endfor return C[jumlah]; endfunction {Algoritma Utama} Deklarasi : jumlah ,d,size,ans,k :integer; s,C:^integer Function CoinChangeDynamic(input jumlah, d[], size, C[], s[] : Integer) →integer
Algoritma : d[] = 1, 5, 10, 25, 50, 100,500,1000; Output<<"Masukan Jumlah Nilai Koin = ";cin>>jumlah; size = sizeof(d)/sizeof(d[0]); C^ = new int[jumlah+1]; s^ = new int[jumlah+1]; ans = CoinChangeDynamic(jumlah, d, size, C, s); Ouput<< "Minimal Koin = " << ans << endl; Ouput<< "Menggunakan Koin: " ; k = jumlah; while(k) { Ouput<< d[s[k]] << " "; k = k - d[s[k]]; endwhile dealloc[] C; dealloc[] s;
3.1.3. Algoritma Traveling Salesman Problem Procedure get(output n,a:integer ) Deklarasi : Algoritma : Output("Enter No. of Cities: "); Input(n); Output("Enter Cost Matrix : "); For i:= i to n do Output(" Enter Elements of Row # : ",i+1); For j:= j to n do Input(a[i][j]); visited[i]=0; endfor endfor Output("The cost list is: "); For( i=0;i
Procedure mincost(input visited:integer;) Deklarasi : city :integer; i,ncity:integer; Algoritma :
visited[city]=1; Output(city+1,"%–>"); ncity= least(city); if(ncity==999) then ncity=0; Output("%d",ncity+1); cost+=a[city][ncity]; return; endif mincost(ncity); endprocedure Procedure put(input cost:integer) Deklarasi : Algoritma : Output("nMinimum cost: "); Output(cost); endprocedure {Algortima utama} Deklarasi : a[10][10],visited[10],n,cost=0:integer; i,j:integer; Procedure get(output n,a:integer ) Function least(input c:integer)→integer Procedure mincost(input visited:integer;) Procedure put(input cost:integer) Algoritma : Procedure get(output n,a:integer ) Output("\n\nThe Path is:\n\n"); mincost(0); put();
3.2. Program 3.2.1. Program Knapsack Problem #include #include #include <stdlib.h> using namespace std; class knapsack { int w[20],v[20],d[10][10],n,c,i,j; public: void input( ); void knap( ); int max(int,int); void output( ); }; void knapsack::input() { cout<<"Knapsack dengan Dynamic programming"<< endl; cout << endl; cout<<"Berapa banyak item yang anda perlukan : "; cin>>n; cout<<"Masukkan kapasitas : "; cin>>c; cout<<"Masukkan "<>w[i]; cout<<"\nmasukkan Profit/Value "<>v[i]; } } void knapsack::knap() { for(i=0;i<=n;i++) d[i][0]=0; for(j=1;j<=c;j++) d[0][j]=0; for(i=1;i<=n;i++) { for(j=1;j<=c;j++)
{ if((j-w[i])<0) d[i][j]=d[i-1][j]; else { d[i][j]=max(d[i-1][j],v[i]+(d[i-1][j-w[i]])); } } } } void knapsack::output() { cout << endl; cout<<"Nilai perhitungan tertinggi untuk "<< n <<" items:"<<endl; for(i=0;i<=n;i++) { for(j=0;j<=c;j++) { cout<<"\t"<b) return a; else return b; } int main() { //system("cls"); knapsack k; k.input(); k.knap(); k.output(); getch(); }
3.2.2. Program coin Change Problem #include #include using namespace std; int CoinChangeDynamic(int jumlah, int d[], int size, int C[], int s[]) { C[0] = 0; for(int j = 1; j <= jumlah; j++) { C[j] = INT_MAX; for(int i = 0; i < size; i++) { if(j >= d[i] && 1 + C[j-d[i]] < C[j] ) { C[j] = 1 + C[j-d[i]]; // i-th denomination used for the amount of j s[j] = i; } } } return C[jumlah]; } int main() { int d[] = {1, 5, 10, 25, 50, 100,500,1000}; int jumlah ;//= 67; cout <<"Masukan Jumlah Nilai Koin = ";cin >>jumlah; int size = sizeof(d)/sizeof(d[0]); int *C = new int[jumlah+1]; int *s = new int[jumlah+1]; int ans = CoinChangeDynamic(jumlah, d, size, C, s); cout << "Minimal Koin = " << ans << endl; cout << "Menggunakan Koin: " ; int k = jumlah; while(k) { cout << d[s[k]] << " "; k = k - d[s[k]]; } delete[] C; delete[] s; return 0; }
3.2.3. Program Traveling Salesman Problem #include<stdio.h> #include <stdlib.h> #include using namespace std; int a[10][10],visited[10],n,cost=0; void get() { int i,j; printf("Enter No. of Cities: "); scanf("%d",&n); printf("\nEnter Cost Matrix: \n"); for( i=0;i
int least(int c) { int i,nc=999; int min=999,kmin; for(i=0;i
cost+=kmin; return nc; } void mincost(int city) { int i,ncity; visited[city]=1; printf("%d ->",city+1); ncity= least(city); if(ncity==999) { ncity=0; printf("%d",ncity+1); cost+=a[city][ncity]; return; } mincost(ncity); } void put() { printf("\n\nMinimum cost:"); printf("%d",cost); } int main() { system("cls"); get(); printf("\n\nThe Path is:\n\n"); mincost(0); put(); getch(); }
BAB IV PENUTUP
4.1. Kesimpulan Pemrograman dinamis merupakan suatu teknik analisa kuantitatif untuk membuat tahapan keputusan yang saling berhubungan. Teknik ini menghasilkan prosedur yang sistematis untuk mencari keputusan dengan kombinasi yang optimal. Pemrograman dinamis membagi permasalahan menjadi beberapa tahap keputusan, dimana hasil keputusan dari satu tahap akan mempengaruhi keputusan dari tiap-tiap tahapan selanjutnya. Dynamic programming dapat didefinisikan juga sebagai suatu pendekatan matematik yang memiliki prosedure sistematis yang dirancang sedemikian rupa dengan tujuan untuk mengoptimalkan penyelesaian suatu masalah tertentu yang diuraikan menjadi sub-sub masalah yang lebih kecil yang terkait satu sama lain dengan tetap memperhatikan kondisi dan batasan permasalahan tersebut.
4.2. Saran Menurut penulis, dengan menggunakan metode dynamic programming sudah sangat
membantu untuk
menyelesaikan suatu
masalah.
Dengan
menggunakan metode ini permasalah yang dianggap rumit pun dapat terselesaikan dengan banyak solusi. Misalkan, solusi knapsack problem, solusi coin change problem, dan traveling salesman problem. Solusi tersebut sudah sangat membantu untuk menyelesaikan suatu permasalahan. Dengan meninjau kelebihan dari dynamic programming kita dapa memecahkan suatu permasalahan yang kompleks menjadi sub-sub masalah yang lebih kecil dan membuat sumber permasalahan
dalam rangkaian proses masalah tersebut menjadi lebih jelas untuk diketahui. Dapat menyelesaikan suatu masalah pemrograman matematik, karena Dynamic Programming cenderung lebih fleksibel dari pada teknik optimasi lain. Prosedur perhitungan dynamic programming juga memperkenankan bentuk analis sensitivitas terdapat pada setiap variabel status maupun pada variabel yang ada pada masing-masing tahap keputusan dan juga dapat menyesuaikan sistematika perhitungannya menurut ukuran masalah yang tidak selalu tetap dengan melakukan perhitungan satu per stu secara lengkap dan menyeluruh.
DAFTAR PUSTAKA http://mohamadrisalrozakamakali.blogspot.com/2013/05/program-dinamis-dynamicprogramming.html http://web.unair.ac.id/admin/file/f_12649_paper_dynamic_programming.pdf http://fileex.blogspot.com/2013/10/skripsi-perancangan-simulasi-dynamic.html http://repo.eepis-its.edu/718/1/1026.pdf https://icomit.wordpress.com/2012/06/02/traveling-salesman-problem-tsp-dalamdefinisi/
Dian Perdhana Putra – 13507096, Teknik Informatika ITB. Jl. Ganesha 10 Bandung. e-mail: [email protected]
