jurusan teknik informatika fakultas teknik · pdf file3.1. algoritma ... sering ditemui dalam...
TRANSCRIPT
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 X2 Xi Xn-1 Xi
S0 S1 S2 Si-1 Si Sn-2 Sn-1 Sn
* 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.
Stage 1
Stage 2
Stage i
Stage n-1
Stage n
r1(S1,X1)
f1(S1,X1)
r2(S2,X2)
f2(S2,X2)
ri(Si,Xi)
fi(Si,Xi)
rn-1(Sn-1,Xn-1)
fn-1(Sn-1,Xn-1)
rn(Sn,Xn)
fn(Sn,Xn)
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 :
**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 3 Tahap 2 Tahap 1
tahap keputusan n. Sedangkan status output dari tahao keputusan n akan menjadi
status input untuk tahap kepututsan berikutnya, yaitu tahap keputusan n-1.
***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 diformulasikan. Selain itu fingsi
transformasi juga menyatakan tentang 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.
Status Input
Tahap 3
Tahap
Keputusan 3
Status Input
Tahap 2
Status output
Tahap 3
Tahap
Keputusan 2
Status Input
Tahap 1
Status output
Tahap 2
Tahap
Keputusan 1
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) = max{f0(y), p1 + f0(y – w1)}
= max{f0(y), 65 + f0(y – 2)}
Y
Solusi Optimum
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)
Barang-i wi pi
1 2 65
2 3 80
3 1 30
M=5
f2(y) = max{f1(y), p2 + f1(y – w2)}
= max{f1(y), 80 + f1(y – 3)}
Y
Solusi Optimum
f1(y) 80 + f1(y – 3) f2(y) (x1*, x2*, x3*)
0 0 80 + (-) = - 0 (0, 0, 0)
1 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) = max{f2(y), p3 + f2(y – w3)}
= max{f2(y), 30 + f2(y – 1)}
Y
Solusi Optimum
f2(y) 30 + f2(y – 1) f3(y) (x1*, x2
*, x3*)
0 0 30 + (-) = - 0 (0, 0, 0)
1 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)
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 "<<n<<" items:"; For(i=1;i<=n;i++) Output<<"\nitemke-"<<i<<" Berat:"; Input>>w[i]; Output<<"\nmasukkan profit/value"<<i<<" :"; Input>>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<<d[i][j]; endfor
endfor endprocedure Function knapsack::max(a :integer,b :integer ) → integer if(a>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<n;i++)
For( j=0;j<n;j++) Output(a[i][j]);
Endfor endfor endprocedure Function least(input c:integer)→integer Int i,nc=999; int min=999,kmin; For(i=0;i<n;i++) if((a[c][i]!=0)&&(visited[i]==0)) then
if(a[c][i]<min) then
min=a[i][0]+a[c][i]; kmin=a[c][i]; nc=i; endif
endif if(min!=999) then cost+=kmin; return nc; endfunction 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 <iostream> #include <conio.h> #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 "<<n<<" items:"; for(i=1;i<=n;i++)
{ cout<<"\nitem ke-"<<i<<" Berat:"; cin>>w[i]; cout<<"\nmasukkan Profit/Value "<<i<<" :"; cin>>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"<<d[i][j];
} cout<<endl;
} } int knapsack::max(int a,int b)
{ if(a>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 <iostream> #include <limits.h> 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<conio.h> 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<n;i++)
{ printf("\n Enter Elements of Row # : %d\n",i+1); for( j=0;j<n;j++) scanf("%d",&a[i][j]); visited[i]=0;
} printf("\n\nThe cost list is:\n\n"); for( i=0;i<n;i++)
{ printf("\n\n"); for( j=0;j<n;j++) printf("\t%d",a[i][j]);
} } int least(int c) {
int i,nc=999; int min=999,kmin; for(i=0;i<n;i++)
{ if((a[c][i]!=0)&&(visited[i]==0)) if(a[c][i]<min)
{ min=a[i][0]+a[c][i]; kmin=a[c][i]; nc=i;
} }
if(min!=999)
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-dynamic-
programming.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-dalam-
definisi/
Dian Perdhana Putra – 13507096, Teknik Informatika ITB. Jl. Ganesha 10 Bandung.
e-mail: [email protected]