Enumerasi Subset dengan Bitmask
Mengiterasi semua subset melalui bilangan bulat
Enumerasi Subset dengan Bitmask adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Himpunan Bagian sebagai Bilangan
Setiap himpunan bagian dari n elemen dapat dipetakan ke satu bilangan bulat. Hitung dari 0 ke atas, dan bit pada setiap bilangan menentukan tepat elemen mana yang termasuk di dalamnya. 🙂
Berapa Banyak Himpunan Bagian
Sebuah himpunan yang berisi n elemen memiliki 2^n himpunan bagian. Jadi, melakukan iterasi pada bilangan bulat dari 0 hingga 2^n dikurangi 1 akan mengunjungi setiap himpunan bagian tepat satu kali.
for mask in range(1 << n):
pass # mask is one subset1 << n Menentukan Jumlah
Operasi geser 1 << n sama dengan 2 pangkat n. Ini adalah cara yang ringkas dan cepat untuk menuliskan batas atas iterasi himpunan bagian Anda.
Baca Bit i
Untuk mengetahui apakah elemen i berada dalam himpunan bagian, periksa bit-nya dengan masker dan 1 yang digeser ke kiri sebanyak i. Hasil yang bukan nol berarti elemen tersebut disertakan.
if mask & (1 << i):
take(items[i])Bangun Daftar Pilihan
Periksa setiap posisi bit dan kumpulkan elemen yang bit-nya bernilai 1. Dengan begitu, satu masker dapat diubah menjadi himpunan bagian konkret yang diwakilinya.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Himpunan Kosong dan Penuh
Masker 0 adalah himpunan bagian kosong, sedangkan masker yang semua bit-nya bernilai 1 mewakili seluruh himpunan. Keduanya diperoleh secara otomatis karena iterasi Anda mencakup setiap nilai.
Jumlahkan Himpunan Bagian
Di dalam iterasi, jumlahkan elemen yang dipilih untuk menghitung nilai setiap himpunan bagian. Inilah inti dari banyak solusi pencarian menyeluruh sederhana.
total = sum(v[i] for i in range(n) if mask & (1 << i))Hitung Bit Bernilai 1
Jumlah elemen yang dipilih sama dengan banyaknya bit bernilai 1 pada masker. Dalam Python, bin(mask).count('1') langsung menghasilkan jumlah tersebut.
size = bin(mask).count("1")Perhatikan Batasnya
Karena ada 2^n himpunan bagian, teknik ini hanya cocok untuk n yang kecil. Sekitar n sama dengan 20 adalah batas praktis untuk enumerasi penuh.
Mengapa Masker Bit Unggul
Satu iterasi bilangan bulat menggantikan iterasi bertingkat yang rumit, dan operasi bit berlangsung cepat. Kodenya tetap singkat, jelas, dan mudah diuji.
Pola yang Dapat Digunakan Kembali
Lakukan iterasi pada masker, uraikan bit-bitnya, hitung nilai himpunan bagian, lalu catat hasil terbaik. Hafalkan templat ini agar banyak masalah himpunan bagian menjadi rutin.
Pemeriksaan Singkat
Anda ingin menguji apakah elemen i disertakan dalam himpunan bagian yang direpresentasikan oleh masker.
Ringkasan
Lakukan iterasi pada masker dari 0 hingga 2^n dikurangi 1, baca bit dengan masker dan 1 yang digeser ke kiri, lalu hitung nilai setiap himpunan bagian. Ini adalah pencarian menyeluruh yang ringkas untuk n kecil. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Enumerasi Subset dengan Bitmask” gratis?
Ya — teks lengkap “Enumerasi Subset dengan Bitmask” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Enumerasi Subset dengan Bitmask”?
Mengiterasi semua subset melalui bilangan bulat Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Enumerasi Subset dengan Bitmask” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Brute Force adalah Strategi yang Valid
- Enumerasi dengan itertools
- Enumerasi Subset dengan Bitmask
- Memangkas Ruang Pencarian dengan Cerdas