My first Magazine pemrograman-kompetitif-dasar | Page 50

4 Brute Force Algoritma 18 Solusi permasalahan Subset Sum yang dioptimasi. 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: function OPTIMIZED S OLVE (i, sum) if i > N then if sum = K then return true else return f alse end if end if if sum > K then return f alse end if option1 ← OPTIMIZED S OLVE (i + 1, sum + a i ) option2 ← OPTIMIZED S OLVE (i + 1, sum) return option1 ∨ option2 end function . Pilih elemen a i . Tidak pilih elemen a i Optimisasi yang dilakukan oleh OPTIMIZED S OLVE pada Algoritma 18 biasa disebut sebagai pruning (pemangkasan). Pruning merupakan optimisasi dengan mengurangi ruang pencarian dengan cara menghindari pencarian yang sudah pasti salah. Meskipun mengurangi ruang pencarian, pruning umumnya tidak mengurangi kompleksitas solusi. Sebab, biasanya terdapat kasus yang mana pruning tidak mengurangi ruang pencarian secara signifikan. Pada kasus ini, solusi dapat dianggap tetap bekerja dalam O(2 N ). Selanjutnya, mari kita lihat contoh yang mana optimisasi dapat mempercepat solusi secara signifikan. Contoh Soal 4.2: Mengatur Persamaan Diberikan sebuah persamaan: p + q + r = 0. Masing-masing dari p, q, dan r harus merupakan anggota dari {a 1 , a 2 , ..., a N }. Diketahui pula bahwa semua nilai {a 1 , a 2 , ..., a N } unik. Berapa banyak triplet hp, q, ri berbeda yang memenuhi persamaan tersebut? Batasan • 1 ≤ N ≤ 2.000 • −10 5 ≤ a i ≤ 10 5 Salah satu solusi untuk menyelesaikan permasalahan tersebut adalah dengan melakukan brute force seluruh nilai p, q, dan r yang mungkin, seperti yang tertera pada Algoritma 19. Karena setiap variabel memiliki N kemungkinan nilai, maka kompleksitas waktu solusi tersebut adalah O(N 3 ). Tentunya terlalu lambat untuk nilai N yang mencapai 2.000. 40