Contoh Permasalahan Yang Diselesaikan Dengan Algoritma Greedy Adalah

%PDF-1.5 %µµµµ 1 0 obj <>>> endobj 2 0 obj <> endobj 3 0 obj <>/ExtGState<>/ProcSet[/PDF/Text/ImageB/ImageC/ImageI] >>/Annots[ 13 0 R 14 0 R] /MediaBox[ 0 0 595.32 841.92] /Contents 4 0 R/Group<>/Tabs/S/StructParents 0>> endobj 4 0 obj <> stream xœ½=ko#7’ßä?è£÷4_Íî`±¸™¼6››Ã ã»7›²­È:Ë–aK›õýúcßl’Ýž‡`©›]¬*Ö»ÈöÛwO§ýo›ëÓê/yûîtÚ\ßnoVŸß^}{ùò¸}ûq³Û?lNûãÃ_ÿºzÿÝ·«÷—_õö²ÚŽ¯.ûú+²êÔê‚h‰º$Ç¡•tuy¯†ýøI®vÏ_Õ­vøk0¿~üú«Ïë¿Ÿ›‹~ýÔˆõC#כ悭͸^Á—O ×WöêÊŒ{^5„®?À×MCÈúÔ\ˆõ¾ÝoNêù=ü¾³€VpãÆ F0õ³ >úÜ�Þþ= 7šúø¯¦_›_W—ÿú«ï€–tJYËdHúg¤¥uO÷¥'kEò¤Ÿó?pNiá@Ò2ƒ Å±¢å$»ºèÚn\]^«yË3Œ yê2<¡—(ÝÛ•£ ÝNý£p§+†vc”K“[±Æ–fìO íPF>5¤C6™ÉÕ¤\ÍÞ×f'´k{C¼(Že-If‡ „� §|²„lKpxßöýÂ9¹DSŠ™¥èŽ)Ä�·ÃRŠÙ²„âÁÎÿXò ƒ±ûÈÐŽ¡P†PæVX­è3cWßøvõ¶`©ÞO§ã}ÍXÙiá°Š¹åFŠÛ®GAe7A9ÈJô>1CÔò1«·�Œßþôݪ{ûÝj½¿¹øé»&2²T‰BjeG‰˜HÎÚÁ2ë�’ˆÇƒ6—êã®!ƒ¶^ÏúZº^,—pÙÊn‰F¢,¥)ãQØ)dŽðåI}Ù«§†°õ½Ý>°Í?ªO¨0Û›†­_Ò©òÄS¡¨'ñÄ—Û§ÛÆÐ{£�À/�«�JR·êúÓ=ø Ï��šø ¿¨�[ûÀÃ�—x7¶"Aà'ñᤕPä›/OŽÖŸ6ÊÉ=jŒ_»V#îÑ,iå°pa”AíÅJR �è±�1gŠ6ž©idüèåщ~[}:«µzz±D¬>(3t¾Ù@2NZ1Æ KÓ3.Ú.™þ£šg«f7®øáJý�®ŸÎ\1*QÕÑŽ–ç$'ÖnÒžé'¦‰°~&éUÄ?¥Íñ÷ —J¯¿5tÔ´ UHä ¨B>àO?)5Ô/ —©h€’˜Ü4Ô*í[&^K.SJÙåÈýÐ0¢¬ŒÂiFZ�Èïaa‘ { —ó¡áÂ’Ka‰—PªH¤ÉÂ.rüL™ ¡¬ï<íì·_~œ•s^ÖLÅ}Œ(B×%zp]½ r„Æó “f�F@€ÆûbPL”(Êðq\½2‹h&=šœ~Pñ]$�â‰ðKƒržaåžFõ·g³†Ö�êþ ¤àµ¬õ¾Ý7B×öðq§¥¿ GÊ›a4³íS1‚²WS:h„Ág=Á”¼ñÜêôpÐ×ÏGè äôìQH²ºv �mx¼q„q‡†�úÛÎX0 K-Ên23þ?&À‰CTÍD€cŽŒ‡Fð`ÈüÜhË¿(ò3À3Ô£EUwïKÞ²¸1ƬDjõ*~q3à„E');#ŠÓLTQ̹“/ôÊ2;K�²Œ‹ÓÊኄä7zôoÀ3$¦Õ‰¬Vâ…˼á¿2.‹r ŠƒìYù|Ì€R~ x¢”+Ñ¡o©ˆ‘**„ÊcU:�EdÍRû"yÞ9=~<Ú =^ßßhn)¢Î?ïOŽ+ÏŽw7^¨ö3«.Æ �X¨Fj*‚ÕRÁìïP-ÝÜ N·¥œA¹ •k3®�_�†¶ÅDðLÂ'ÞÁŒ”ÐöÚvX¸UQ¢jEd�¡¥[Z'v¹u Vý|YdLEß+7ç¦[¹½u¬Õ²p:‚ÉÇ»[àÿ›‡Þjíw igø w§öX twOÈƳ^å>š×ë(ÎgeòŒÙf׳¥Öí;>8QüºtBcÉp¦ÔÁUÜS®2Šxœö÷ % i�ЉÁ¦] …r5˜a&´S7¢�—ú@O¶‡ýi¿±žˆY› öopæââw#TmÂY‹% À=ìù‡d^wžC�KDÞG“„�O§ÍiÇ@!럳Ò*aõæ¼è°)Ö kø¡,x8¬ØDîKe§:!‹&j;áÐ@‡îõN5ßa_²�l�m_g«/Öb^�C %®6–à²K ÄjÓPb4ï1 ]‚÷™ÅÕ!pÆ‘ƒÖŠESŠ+X±™PÐÛ‹MWx pkƒ p}5Œ`ŽÖRMð¢lߧ³í^Œ £�E@‹¾�ñv\:TBü�ý îYû“b1KýËfÀR{4T§;F|x(gÏ— t•õU}!ò+Æ[™hæ„þÄÜ*Õíô‘¡L¬kDc1&ż÷;ƒ«tjyIVò³è %(�B\{,;v¯÷þв¶¨ˆ]&«û€éLJ³åyó¤û¸Z§K5eÑlK¸ 9@üñÎk£?3ø÷×Ä•°]‰…L?í1ÐÖ,.Șò‰`AÂg‹ò¨²Ö!ëpz®o0GÊ>_%×téL|DÝ Ç.áQé@úÜF9n‘qÜr©ßÖ¹zóUŽ›¨¨VéÎ{n.Û.yPk�@ôe$H �Øy@æF¦ÍŠýñXtòÊ[P€‡œþmzƒÏÓåýÁÝë,·M– ‘/a(§cKÆœTõ:ãÜTŽs>@Åâ•oH‡j?“v<8Sw*‰—õ®¯æ†µ¹7`œ#ÿPâQy܃(»KŠx†cµûº…‰t6ñå9£²¬~7 ˆbÂ)JL‡iœô+-f8í%¦�5¢óú,µ!L<óÎz]üÙîšaÆ;C¬ÝÉek c™ þlUËEH:F©üUÅ06tèCȇíèr1ôæ�ÂF,Ãœw¼å •GW}?gs±C0Ò_4§Ð_žê†ó?J€¨©»êK'g·È˜Î��ÄICÚ¶ZêJ -‘!Ø‹Å{µß^.KØ(¨Ô;„1Ý�6Ý :Û~'„AU“K±ÐzÐÙ^¸]†ž{ƒqy‹»¦• C¦=9ˆjwö´^}â%®t OÁ}¹Þ?ët0BZyê^£¢Ý�Æàô¤‹ßF¦|Ô©¼VÜí¾?†z1ô~�þ‰ýœƒnv�öG—)ƒaVÉ´Âõ‡I�Ÿ˜Ó-†µÚo{\Êþp€ÆÕDŒ½>œ}àÆ4ì*É¢³‹&($zÑ`ž[‡Þa»òU-C)1<Àk'ŒÁúæÑq†ªržÃé‘!¥þß¹8rû¼2%ÂdÊí¿pÇ=Ú^G±j¦¾ÞÀ þ(N_«hYßp«½Ùé@*|¨}!až ×Gùà-¦fÂö©ÕÄþø§ Ô¢˜)‘ΉCA¹Ÿ[!•š»BVà w}Ìí 󓣫¡í>[ÙŠXtô«åÃêD­àýÿVšï”RH2"ÙW0òÚølõS2¥e0 S-¬Æé�ë�'Á¯/G¨žÿ2Ç~À#˜mÛœ®k1ÚY}öKðì„åt\ ‡*íW��rb;�’VJKïdP­€g5wlÊ®R�Opûl}Ù˜žºóáì˜V\pr"Ƶ|úDBK'û¤r{gÎêèøãÊE#€�+wR£zkûhï(T�aÃQŽ Úü=áé×ÆãêlOæH\ñbl‚À®_ÿk†¿Æ=6}”¥´æú{Ìû'‚·ŽØDòÈFkP—l÷Aۢõ>�©Q¬[cà͈‚˜2e3õ/¯ f�©ZXË«]ò^Ú® °–ÿiõjHèÝB{`àãàûíá%¸1Ÿ`9†Á�U)àHKeÌSSð#Xn¶“P½€i6‹?&éœA`c—ù¦Rq°Ûõm?Wa›Ì<-ö¼±ígÒoÙ�Þr©‹¿ƒî¾Ã-XÌMHÂòõõxu]¯šlY±¸qfH;qk,‘±Æˆ¶î3U ¤¡1[h"ÊBžÜõ¡tæ( ½œÎéô~‘¹ �°Ûø6`§O– ,”ay æ>IÊþ`�NXöcŒ}ZgðeC<:�­'Å]­µÒX+—ÁŸ=gAJ}ˆ ´€^ ªð{C�ÝúÄlÐÛ°¿©TŒÉÃ\XKè ï=…‚¼ 39¾º€ _k@µðd† a9åœ µ¦ßöI$³¨2ÅdÅÒ"ߦË[9–a¯]ëžâÀ/nÜ-í†ÐE†Ín‚��îoA¢ôi¦‚êŒlðŠÅ£‰·úð©Ïƒ {ˆo*Q“Wp0Æ �­“\)ö•,Œ�P±øÂíÙ´X „9§l65è p’Ù-͸> ù‡ïÍI4:k*†sÒ6Pãù

Hey kawan blogger, sudah dibilang kan saya itu kalo udah sekali nulis maunya nulis terus. hehe :p

Kali ini saya mau berbagi tentang program C++ yang menggunakan Algoritma Greedy.

Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi. Prinsip greedy: “take what you can get now!”. Algoritma greedy membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Pada setiap langkah, kita membuat pilihan optimum lokal (local optimum) dengan harapan bahwa langkah sisanya  mengarah ke solusi optimum global (global optimum). Dengan kata lain algoritma greedy melibatkan pencarian sebuah himpunan bagian, S, dari himpunan kandidat, C; yang dalam hal ini, S harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimisasi oleh fungsi obyektif.

Nah di bawah ini merupakan contoh coding programnya:

void sort(int[],int);

int x[size],i,n,uang,hasil[size];

printf("\nbanyaknya jenis koin: ");

printf("\nmasukkan jenis koin (Rp): \n");

printf("\njenis koin yang tersedia (Rp): \n");

printf("%d \t",x[i]); }

printf("\n\nmasukkan nilai yang ingin dipecah: Rp ");

printf("\n\nhasil algoritma greedynya adalah: \n");

printf("\akoin Rp %d",x[i]);

printf("-an sebanyak: %d keping",hasil[i]);

void sort(int a[],int siz) {

for(pass=1;pass<=siz-1;pass++) {

for(j=0;j<=siz-2;j++) {

Output dari program di atas adalah sebagai berikut:

Logika dari coding program di atas adalah sebagai berikut:

peryataan conio.h. adalah library pada C yang digunakan untuk mengkoneksikan pernyataan clrscr() dengan program yang kita buat. Tanpa menggunakan library ini, kita tidak bisa menggunakan fungsi prototype seperti: gotoxy(), clrscr(), clreol().

Dalam c++ jika kita menginginkan penggunaan input dan output, atau bisa diartikan sebagai standard library yang berfungsi untuk I/O  package maksudnya digunakan jika kita ingin pada program kita menggunakan fungsi standard input atau output bisa dikatakan seperti portable input/output package. Tanpa menggunakan library ini, kita tidak bisa menggunakan perintah-perintah input/output pada program kita.

Library di atas berguna untuk menentukan size dari inputan banyak datanya adalah 99, artinya jika data lebih banyak dari 99, maka program akan berhenti mengeksekusi.

Pernyataan diatas adalah main procedure (prosedur utama dalam program ini). Pada program ini, program utama berbentuk prosedur untuk mengurutkan data yang kita input, disini yang akan diurutkan adalah variable masukan dari int[] dan int.

Pernyataan di atas digunakan sebagai badan program. Fungsinya sama seperti public.static.void.main(String args[]) { pada bahasa pemrograman java.

Pernyataan di atas digunakan untuk membersihkan layar ketika program dieksekusi.

Pernyataan di atas digunakan untuk mendefinisikan variable yang akan digunakan dalam programnya. Tanda kurung siku [ ] menandakan variable tersebut bertipe array.

Pernyataan printf di atas digunakan untuk mencetak tulisan yang ada diantara tanda kutip “ ”. \n digunakan untuk member jeda (enter) pada saat program dieksekusi.

Pernyataan scanf digunakan untuk menyimpan angka yang kita input ketika program dieksekusi. Disini terdapat %d yang mengartikan data inputan akan ditampilkan dalam bentuk decimal, dan &n mengartikan data inputan akan disimpan sementara pada variable n.

Pernyataan for di atas digunakan sebagai kondisi perulangan pada program, sedangkan pernyataan hasil[i]=uang/x[i]; digunakan sebegai rumus perhitungan untuk mendapatkan kombinasi koin apa saja yang digunakan untuk menukarkan koin yang ingin kita tukarkan dengan koin yang tersedia, lalu pernyataan uang=uang%x[i]; digunakan untuk menentukan berapa banyaknya kombinasi koin dalam pertukaran koinnya.

berguna unutk membaca sebuah karakter, bisa juga membaca tombol, getch() tidak akan menampilkan karakter dari tombol yang ditekan. Sebuah getch() bisa pula digunakan untuk menunggu sembarang tombol ditekan. Pada keadaan seperti ini, hasil dari fungsi ini tidak perlu diletakkan ke variable, atau dipascal dapat diartikan sebagai readln

angka 0 ini akan dikembalikan kepada sistem operasi. Nilai ini digunakan oleh sistem operasi untuk disimpan di variabel ERRORLEVEL pada MS DOS, dimana 0 artinya ‘sukses’.

Blok pernyataan di atas digunakan untuk mengurutkan angka yang telah kita input pada saat program dieksekusi.

Sekian yang dapat saya bagian mengenai Algoritma Greedy dan contoh programnya. Semoga bermanfaat bagi yang membacanya. Akhir kata, terima kasih dan ...

Algoritma greedy adalah algoritma apa pun yang mengikuti metode heuristik dalam pemecahan masalah untuk membuat pilihan optimal secara lokal di setiap tahap.[1] Dalam banyak permasalahan, strategi greedy tidak menghasilkan solusi optimal, tetapi suatu heuristik greedy dapat menghasilkan solusi optimal lokal yang mendekati solusi optimal global dalam jangka waktu yang wajar.

Misalnya, strategi greedy untuk masalah penjual keliling (yang memiliki kompleksitas komputasi tinggi) adalah heuristik berikut: "Pada setiap langkah perjalanan, kunjungi kota terdekat yang belum dikunjungi." Heuristik ini tidak bertujuan untuk menemukan solusi terbaik, tetapi ia berakhir dalam sejumlah langkah yang wajar. Yang mana menemukan solusi optimal untuk masalah yang kompleks biasanya memerlukan banyak langkah yang tidak masuk akal. Dalam optimasi matematis, algoritma greedy secara optimal dapat menyelesaikan masalah kombinatorial yang memiliki sifat matroid dan memberikan hampiran faktor konstan untuk masalah optimasi dengan struktur submodular.

Algoritme greedy menghasilkan solusi yang baik pada beberapa masalah matematis, tetapi tidak pada masalah lainnya. Sebagian besar masalah yang algoritma greedy kerjakan memiliki dua properti:

Dimulai dari A, algoritma greedy yang mencoba menemukan nilai maksimum dengan mengikuti kemiringan terbesar akan menemukan maksimum lokal di "m", tanpa menyadari maksimum global di "M".

Untuk mencapai nilai terbesar, pada setiap langkah, algoritma greedy akan memilih apa yang tampak sebagai pilihan langsung yang optimal, sehingga ia akan memilih 12 dan bukannya 3 pada langkah kedua, dan tidak akan mencapai solusi terbaik, yaitu 99.

Algoritme greedy gagal menghasilkan solusi optimal untuk banyak masalah lain dan bahkan mungkin menghasilkan solusi unik yang paling buruk . Salah satu contohnya adalah masalah travelling salesman yang disebutkan di atas: untuk setiap jumlah kota, terdapat penetapan jarak antar kota dimana heuristik tetangga terdekat menghasilkan tur terburuk yang mungkin terjadi.[3] Untuk kemungkinan contoh lainnya, lihat efek cakrawala.

Algoritme greedy dapat dikategorikan sebagai algoritma yang 'berpandangan sempit', dan juga 'tidak dapat dipulihkan'. Algoritma ini hanya ideal untuk permasalahan yang memiliki 'substruktur optimal'. Meskipun demikian, untuk banyak masalah sederhana, algoritma yang paling cocok adalah algoritma greedy. Namun, penting untuk dicatat bahwa algoritma greedy dapat digunakan sebagai algoritma seleksi untuk memprioritaskan pilihan dalam pencarian, atau algoritma branch-and-bound. Ada beberapa variasi pada algoritma serakah:

Algoritma greedy memiliki sejarah panjang dalam studi optimasi kombinatorial dan ilmu komputer teoretis. Heuristik serakah diketahui memberikan hasil yang kurang optimal pada banyak masalah,[4] sehingga pertanyaan yang wajar adalah:

Sejumlah besar literatur menjawab pertanyaan-pertanyaan ini untuk kelas masalah umum, seperti matroid, serta untuk masalah khusus, seperti set cover.

Matroid adalah struktur matematika yang menggeneralisasi konsep independensi linier dari ruang vektor ke himpunan sembarang. Jika suatu masalah optimasi mempunyai struktur matroid, maka algoritma greedy yang sesuai akan dapat menyelesaikannya secara optimal.[5]

Sebuah fungsi f {\displaystyle f} didefinisikan pada himpunan bagian dari suatu himpunan Ω {\displaystyle \Omega } disebut submodular, jika untuk setiap S , T ⊆ Ω {\displaystyle S,T\subseteq \Omega } kita mempunyai f ( S ) + f ( T ) ≥ f ( S ∪ T ) + f ( S ∩ T ) {\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)} .

Misalkan seseorang ingin mencari sebuah himpunan S {\displaystyle S} yang memaksimalkan f {\displaystyle f} . Algoritma greedy, yang membangun satu himpunan S {\displaystyle S} dengan menambahkan elemen secara bertahap yang meningkatkan f {\displaystyle f} paling banyak pada setiap langkah, menghasilkan keluaran sebuah himpunan yang paling sedikit ( 1 − 1 / e ) max X ⊆ Ω f ( X ) {\displaystyle (1-1/e)\max _{X\subseteq \Omega }f(X)} .[6] Artinya, keserakahan bermain dalam faktor konstan ( 1 − 1 / e ) ≈ 0.63 {\displaystyle (1-1/e)\approx 0.63} sama baiknya dengan solusi optimal.

Jaminan serupa dapat dibuktikan ketika kendala tambahan, seperti batasan kardinalitas, [7] diterapkan pada keluaran. Meskipun sering kali diperlukan sedikit variasi pada algoritma greedy. Lihat[8] untuk ikhtisarnya.

Masalah lain yang mana algoritma greedy memberikan jaminan yang kuat, tetapi bukan solusi optimal, termasuk

Banyak dari permasalahan ini memiliki batas bawah yang sesuai, yaitu algoritma greedy tidak berkinerja lebih baik daripada jaminan dalam kasus terburuk.

Algoritme greedy biasanya (tetapi tidak selalu) gagal menemukan solusi optimal secara global karena algoritma tersebut biasanya tidak beroperasi secara mendalam pada semua data. Algoritma jenis ini dapat membuat komitmen pada pilihan-pilihan tertentu terlalu dini, sehingga mencegah mereka untuk menemukan solusi terbaik secara keseluruhan nantinya. Misalnya, semua algoritma pewarnaan serakah yang diketahui untuk masalah pewarnaan graf dan semua masalah NP-lengkap lainnya tidak secara konsisten menemukan solusi optimal. Namun, algoritma jenis ini berguna karena mereka cepat berpikir dan sering memberikan hampiran yang baik secara optimal.

Jika algoritma greedy dapat dibuktikan menghasilkan optimal global untuk kelas masalah tertentu, biasanya algoritma ini menjadi metode pilihan karena lebih cepat dibandingkan metode optimasi lain seperti pemrograman dinamis. Contoh algoritma greedy tersebut adalah algoritma Kruskal dan algoritma Prim untuk mencari pohon rentang minimum serta algoritma untuk mencari pohon Huffman optimal.

Algoritmq greedy juga muncul di perutean jaringan. Dengan menggunakan routing serakah, sebuah pesan diteruskan ke node tetangga yang “paling dekat” dengan tujuan. Gagasan tentang lokasi sebuah node (dan karenanya "kedekatan") dapat ditentukan oleh lokasi fisiknya, seperti dalam perutean geografis yang digunakan oleh jaringan ad hoc . Lokasi mungkin juga merupakan konstruksi buatan seperti dalam perutean dunia kecil dan tabel hash terdistribusi.

[email protected] https://teknokrat.ac.id/en/ https://spada.teknokrat.ac.id/Read less

Knapsack merupakan suatu permasalahan bagaimana memilih objek dari sekian banyak objek dan berapa besar objek tersebut akan disimpan sehingga diperoleh suatu penyimpanan yang optimal. Knapsack dapat diilustrasikan sebagai suatu kantong atau media penyimpanan. Kantong atau media penyimpanan tersebut hanya dapat menyimpan beberapa objek dengan batasan objek tersebut sama atau lebih kecil dari kapasitas media penyimpannya. Terkadang keterbatasan manusia dalam menyelesaikan masalah knapsack tanpa menggunakan alat bantu merupakan salah satu kendala dalam pencarian solusi optimum. Dengan adanya algoritma penyelesaian pada masalah integer knapsack diharapkan dapat membantu dalam proses pemilihan barang. Dengan adanya proses pemilihan barang yang tepat maka dapat membantu mendapatkan keuntungan maksimum. Penelitian ini dilakukan di industri perdagangan UD. BINTANG TANI di Jl. Yos. Sudarso Kecamatan Semboro Kabupaten Jember. Pengambilan data dilakukan dengan metode wawancara dan data yang diambil berupa data harga beli, harga jual, dan banyaknya barang. Untuk menerapkan data tersebut dilakukan pengidentifikasian untuk mencari keuntungan ( ) dan ( ). Algoritma yang digunakan pada permasalahan integer knapsack ini adalah algortima Greedy dan Dynamic Programming. Data penelitian yang digunakan yaitu data sekunder. Tujuan dari peneliti adalah untuk mencari keuntungan maksimum di UD. BINTANG TANI pada permasalahan integer knapsack dengan menggunakan algoritma Greedy dan Dynamic Programming, serta membandingkan algoritma Greedy dan Dynamic Programming pada permasalahan integer knapsack dari segi hasil dan kompleksitas waktu. Hasil penelitian menunjukkan: (1) Keuntungan maksimum penggunaan algoritma Greedy adalah sebesar Rp 687.500,- dengan bobot 479 kg. (2) Keuntungan maksimum penggunaan algoritma Dynamic Programming adalah sebesar Rp 691.500,- dengan bobot 499 kg. (3) Algoritma Greedy dan Dynamic Programming pada kasus permasalahan integer knapsack berdasarkan banyak langkah yang dibutuhkan diperoleh hasil pencarian bahwa pada algoritma Greedy diperlukan proses perbandingan sebanyak kali, maka kompleksitas waktunya adalah ( ). Pada algoritma Dynamic Programming jumlah langkah yang diperlukan untuk mencapai solusi optimal adalah sebanyak , maka kompleksitas waktunya adalah ( ). Sehingga algoritma Dynamic Programming mempuyai jumlah kompleksitas yang lebih besar dibandingkan dengan algoritma Greedy. Dari hasil di atas dapat disimpulkan bahwa dari segi hasil algortima Dynamic Programming lebih mencapai hasil yang maksimum daripada algoritma Greedy tetapi dalam segi kompleksitas waktu algoritma Dynamic Programming mempunyai kompleksitas waktu yang lebih besar daripada algoritma Greedy.

��ࡱ� > �� � ���� ���� � � � � ������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������ �� �( � � � � J ; �D � � F i l e L a i n � l a n j u t 1 . p p t �F � � K n a p S a c k � k n a p s a c k . p p t x �V � �" A l g o r i t m a K r u s k a l � k r u s k a l . p p t x �V � �" A l g o r i t m a K r u s k a l � k r u s k a l . p p t x �V � �" A l g o r i t m a K r u s k a l � k r u s k a l . p p t x �J � ! � A l g o r i t m a P r i m � p r i m . p p t x �J � $ � A l g o r i t m a P r i m � p r i m . p p t x �F � ' � D i j k s t r a � d j i k s t r a . p p t x �D � , � F i l e L a i n � l a n j u t 1 . p p t �F � / � K n a p S a c k � k n a p s a c k . p p t x �V � 1 �" A l g o r i t m a K r u s k a l � k r u s k a l . p p t x �J � 7 � A l g o r i t m a P r i m � p r i m . p p t x �F � ; � D i j k s t r a � d j i k s t r a . p p t x �� / � 0 � �� �D A r i a l H�� x�b��� X�� ��� ��� l�� `�� u�b`�� � �D C a l i b r i x�b��� X�� ��� ��� l�� `�� u�b`�� � " �D W i n g d i n g s ��� X�� ��� ��� l�� `�� u�b`�� � 0 �D S y m b o l g s ��� X�� ��� ��� l�� `�� u�b`�� � @ �D C o u r i e r N e w X�� ��� ��� l�� `�� u�b`�� � 1P �D T i m e s N e w R o m a n ��� ��� l�� `�� u�b`�� � � � @ � . � @ �n ��? " d � d @ ��� �� �� @@ `` �� H �@ �� l a � �0 � � �� � � �� � @ � � � � � �* ���� ʚ;��� ʚ; <

Algoritma adalah langkah dalam mencari solusi atas sebuah masalah. banyak sekali algoritma yang dapat kita gunakan dalam membangun sebuah program , salah satunya adalah algoritma greedy.

Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi. Greedy sendiri diambil dari bahasa inggris yang artinya rakus, tamak atau serakah .Prinsip algoritma greedy adalah: “take what you can get now!”.

– Memilih beberapa jenis investasi (penanaman modal) – Mencari jalur tersingkat dari Bandung ke Surabaya – Memilih jurusan di Perguruan Tinggi – Bermain kartu remi

Algoritma greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.

Persoalan optimasi (optimization problems): persoalan yang menuntut pencarian solusi optimum. Persoalan optimasi ada dua macam: Maksimasi (maximization) dan Minimasi (minimization) Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin. Elemen persoalan optimasi: kendala (constraints) danfungsi objektif(atau fungsi optiamsi)

Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum. Untuk LA kali ini saya akan menjelaskan program pengambilan koin, yang menggunakan algoritma greedy. Bahasa pemrograman yang saya gunakan adalah bahasa C++, dan software yang digunakan adalah borland C.

Keep your knowledge by sharing to everyone