Untuk menjelaskan konsep DP Bitmask, saya gunakan salah satu contoh soal di SPOJ yang saya rasa adalah contoh straight-forward yang bisa langsung dicoba implementasinya oleh pembaca.
ASSIGN
http://spoj.pl/problems/ASSIGN
Solusi: DP BITMASK
Prerequisite: Dynamic Programming
by Risan (ptrrsn_1)
Soal ini dapat diselesaikan dengan dp bitmask. Kompleksitas waktunya O(n 2^n).
Konsep DP bitmask: Solusi optimal untuk himpunan A dengan jumlah anggota K, di mana K > 0, diperoleh dari solusi subhimpunan-subhimpunan dari himpunan A tersebut. Implementasi himpunan dan subhimpunan-subhimpunan ini menggunakan bitmask.
Untuk contoh soal ASSIGN, solusi optimal untuk himpunan A bisa diperoleh dari subhimpunan-subhimpunan A yang memiliki anggota sebesar K – 1.
Untuk bitmask yang digunakan, kita gunakan konvensi berikut.
Bit paling kiri kanan (istilahnya Least Significant Bit / LSB) menandakan status orang ke-(n – 1), dan bit paling kanan kiri (Most Significant Bit / MSB) menandakan status orang ke-0.
Misalkan bitmask 7 orang:
1111111 6543210
Nomor di bawahnya menandakan orang yang ditunjukkan oleh bit bersangkutan.
Aturan tersebut mempermudah kita memproses sebuah bitmask. Misalkan untuk mengecek apakah ada orang ke-i di himpunan tersebut, kita bisa tes dengan statement berikut:
if (bitmask & (1 << i)) { ... }
Untuk menghapus orang ke-i dari bitmask, jika kita bisa memastikan orang tersebut sebelumnya ADA di dalam bitmask tersebut bisa dilakukan sebagai berikut:
bitmask -= 1 << i;
Untuk mengubah status orang ke-i pada bitmask (statusnya 1 jika orang itu ada di bitmask, dan 0 jika orang itu tidak ada di bitmask), kita bisa lakukan:
bitmask ^= 1 << i;
Pengubahan status ini maksudnya adalah kita memasang orang itu di bitmask jika sebelumnya orang itu tidak ada di bitmask dan kita mencabut orang itu dari bitmask jika sebelumnya dia sudah ada di bitmask (0 jadi 1 atau 1 jadi 0).
=================================================
Trik:
=================================================
Nah, terlepas dari DP Bitmask, ada sebuah trik untuk mempermudah coding di soal ini. Misalkan hanya ada dua kemungkinan isi variable bol, yaitu 1 atau 0, dan ada statement:
if (bol == 1)
x += y;
Statement itu bisa juga ditulis sebagai:
x += bol * y;
Kedua statement itu sama karena jika bol == 1, kita tambahkan x dengan y (atau 1 * y), selain itu kita tidak tambahkan dengan y (kali dengan 0). Variable seperti ini disebut sebagai variable indikator. Untuk latihan, coba modifikasi code di bawah dengan trik ini sehingga menghasilkan code yang lebih pendek.
Variable Indikator ini meskipun merupakan konsep yang sederhana, bisa digunakan untuk analisis statistik yang cukup kompleks. Misalkan untuk perhitungan kompleksitas harapan Quicksort yang Θ(n lg n) (terlalu matematis untuk dibahas di tutorial ini, karena bisa lebih panjang dari solusi problem ASSIGN ini).
=================================================
Dalam perhitungan dp ini, kita menganggap urutan pekerjaannnya terurut mulai dari indeks terkecil hingga indeks terbesar. Dan dari setiap k buah pekerjaan pertama, kita pasangkan mereka dengan orang-orang yang akan menjadi pelakunya (sebanyak k orang). Sehingga, untuk setiap k pekerjaan pertama kita memiliki sebuah bitmask yang banyak anggotanya adalah k, yaitu himpunan orang-orang yang akan menjadi pelakunya.
Perhatikan, semua pengindeksan untuk kode di bawah ini menggunakan sistem 0-based.
Solusi top-down:
dp[bm] = 0;
// banyaknya orang di himpunan itu sebesar banyaknya digit 1 di bitmask bm
jumlah_orang_di_himpunan = __builtin_popcount (bm);
// n ini adalah banyaknya seluruh orang di soal (dapat dari input)
for (int i = 0; i < n; i++) {
// Jika ada orang ke-i di himpunan bm,
if ( (bm & (1 << i)) > 0) {
// bm - (1 << i) sama aja menghilangkan bit 1 ke-i karena bit ke-i pasti 1
// sebelum operasi ini berlangsung
if (M[i][jumlah_orang_di_himpunan - 1] == 1)
dp[bm] += dp[bm - (1 << i)];
}
// Jika tidak ada, abaikan
}
Jadi, kalau dibuat fungsi rekursinya:
LL f (int bm) {
// ada satu kemungkinan assigment untuk himpunan kosong
// yaitu tidak memasang siapapun dengan pekerjaan manapun
if (bm == 0)
return 1;
LL &ret = dp[bm];
if (ret != -1)
return ret;
ret = 0;
int jumlah_orang_di_himpunan = __builtin_popcount (bm);
for (int i = 0; i < n; i++) {
if ((bm & (1 << i)) > 0 && M[i][jumlah_orang_di_himpunan – 1])
ret += f (bm - (1 << i));
}
return ret;
}
sebelumnya, semua isi dp dibuat -1. Caranya:
memset (dp, -1, sizeof (dp));
Pemanggilan fungsi f:
printf ("%lld\n", f((1 << n) - 1));
Jadi, kita mau mencari solusi optimal untuk bitmask 111…1 yang jumlah digit 1 nya sebesar n.
Contoh eksekusi:
Misalkan sang matrix M isinya:
1 0 1 0 1 1 1 1 0
n = 3
Maka, banyaknya kemungkinannya adalah dp[111]
dp[000] = 1 dp[001] = dp[000]
orang ke-1 tidak bisa melakukan pekerjaan ke-0 (M[1][0] == 0), maka:
dp[010] = 0
orang ke-0 tidak bisa melakukan pekerjaan ke-1 (M[0][1] == 0), tapi orang ke-1 bisa melakukan pekerjaan ke-1 (M[1][1] == 1), maka:
dp[011] = dp[001] dp[100] = dp[000]
hanya orang ke-2 yang bisa melakukan pekerjaan ke-1
dp[101] = dp[001]
kedua orang bisa melakukan pekerjaan ke-1
dp[110] = dp[100] + dp[010]
semua kecuali orang ke-2 bisa melakukan pekerjaan ke-2
dp[111] = dp[110] + dp[101]
Versi bottom up dari dp ini sebagai berikut (menggunakan trik yang sudah dijelaskan):
dp[0] = 1;
for (int bm = 1; bm < (1 << n); bm++) {
int jumlah_orang = __builtin_popcount (bm);
int indeks_pekerjaan = jumlah_orang - 1;
for (int i = 0; i < n; i++) {
if (bm & (1 << i))
dp[bm] += M[i][indeks_pekerjaan] * dp[bm - (1 << i)];
}
}
printf ("%lld\n", dp[(1 << n) - 1]);
Perhitungan kompleksitas: Karena ada 2^n kemungkinan bitmask yang dihitung, dan untuk perhitungan masing-masing bitmask kita melakukan suatu iterasi linear O(n), maka kompleksitasnya O(n 2^n). Memory yang diperlukan sebesar O(2^n) untuk menyimpan tabel dp.
Special thanks to Timotius Sakti and Hendri Tan
Thanks to Teddy for correcting a mistake about LSB and MSB.