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