My first Magazine pemrograman-kompetitif-dasar | Page 49

4.3 Optimisasi Teknik Brute Force Sebagai contoh, kita kembali ke permasalahan Subset Sum . Untuk setiap elemen, terdapat dua kemungkinan, yaitu memilih bilangan tersebut untuk dimasukkan ke subhimpunan atau tidak. Selanjutnya, kita akan menelusuri semua kemungkinan pilihan yang ada. Jika terdapat pemilihan yang jumlahan elemen-elemennya sama dengan K, maka terdapat solusi. Hal ini dapat dengan mudah diimplementasikan secara rekursif. Selanjutnya, mari kita analisis performa strategi brute force untuk permasalahan Subset Sum . Untuk setiap elemen, terdapat 2 pilihan, yaitu dipilih atau tidak. Karena terdapat N elemen, maka terdapat 2 N kemungkinan. Maka, kompleksitas solusi brute force adalah O(2 N ). Untuk nilai N terbesar, 2 N = 2 15 = 32.768, yang masih cukup dalam operasi komputer per detik pada umumnya (100 juta). Algoritma untuk menyelesaikan permasalahan Subset Sum dapat ditemukan pada Algoritma 16 serta Algoritma 17. Algoritma 16 Solusi permasalahan Subset Sum . 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: function SOLVE (i, sum) if i > N then if sum = K then return true else return f alse end if end if option1 ← SOLVE (i + 1, sum + a i ) option2 ← SOLVE (i + 1, sum) return option1 ∨ option2 end function . Pilih elemen a i . Tidak pilih elemen a i Algoritma 17 Fungsi pemanggil solusi. function SOLVE S UBSET S UM () return SOLVE (1, 0) 3: end function 1: 2: 4.3 Optimisasi Teknik Brute Force Bisakah solusi pada Algoritma 16 dibuat menjadi lebih cepat? Perhatikan kasus ketika sum telah melebihi K. Karena semua a i bernilai positif, maka sum tidak akan mengecil. Karena itu, bila sum sudah melebihi K, dipastikan tidak akan tercapai sebuah solusi. Dari sini, kita bisa mengoptimisasi fungsi SOLVE menjadi fungsi OPTIMIZED S OLVE yang akan menghentikan suatu penelusuran kemungkinan apabila jumlahan elemen yang dipilih sudah melebihi K. Algoritma penyelesaian Subset Sum dengan optimasi tersebut dapat dilihat di Algoritma 18. 39