Penerapan Pemrograman Dinamis Metode Maximum Independent Set Pada Permasalahan E-Olymp 8744 Expedition.

Rahastri, Intan Kusuma (2022) Penerapan Pemrograman Dinamis Metode Maximum Independent Set Pada Permasalahan E-Olymp 8744 Expedition. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840000020-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (2MB)

Abstract

Permasalahan dalam tugas akhir ini adalah “Expedition” pada situs penilaian daring E-Olymp nomor soal 8744. Dalam permasalahan ini diminta untuk mencari jumlah kandidat maksimal untuk dikirim ekspedisi ke sistem bintang tetangga jika setiap kandidat mempunyai 0 atau 1 orang yang tidak diinginkan untuk pergi bersama. Permasalahan direpresentasikan sebagai graph dengan menghubungkan nomor kandidat dengan nomor kandidat yang tidak diinginkannya. Pemrograman dinamis metode Maximum Independent Set diimplementasikan untuk mencari kandidat maksimal yang dapat dikirim ekspedisi. Pemrograman dinamis metode Maximum Independent Set diimplementasikan dengan menggunakan bahasa pemrograman C++. Dari hasil uji coba yang telah dilakukan, didapatkan kesimpulan bahwa penyelesaian menggunakan pemrograman dinamis metode Maximum Independent Set membutuhkan rata-rata waktu sebesar 0.412 detik dan rata-rata memori sebesar 50.9832 MB.
=================================================================================================================================
The problem in this final project is "Expedition" on the online assessment site E-Olymp with problem number 8744. The problem asks to find the maximum number of candidates that can be sent on an expedition to the neighboring star system if each candidate has 0 or 1 person he doesn't want to go with. This problem is represented as a graph by associating a candidate with its unwanted candidate. Dynamic programming with Maximum Independent Set method implemented to find the maximum candidate that can be sent to an expedition. The dynamic programming with Maximum Independent Set method is implemented using the C++ programming language. From the experiments that have been conducted, it was concluded that the solution using the dynamic programming with Maximum Independent Set method requires average time of 0.412 second and average memory of 50.9832 MB.

Item Type:	Thesis (Other)
Additional Information:	RSIf 003.85 Rah p-1 2022
Uncontrolled Keywords:	Graph, Maximum Independent Set, Pemrograman Dinamis. Dynamic Programming, Graph, Maximum Independent Set.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Mr. Marsudiyana -
Date Deposited:	25 May 2026 03:57
Last Modified:	25 May 2026 03:57
URI:	http://repository.its.ac.id/id/eprint/133387

Actions (login required)

View Item