Enumerowanie podzbiorów za pomocą masek bitowych
Iterowanie po wszystkich podzbiorach za pomocą liczb całkowitych
Enumerowanie podzbiorów za pomocą masek bitowych to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Podzbiory jako liczby
Każdy podzbiór n elementów można odwzorować na jedną liczbę całkowitą. Wystarczy odliczać od zera, a bity każdej liczby wskażą dokładnie, które elementy należą do podzbioru. 🙂
Ile istnieje podzbiorów
Zbiór n elementów ma 2^n podzbiorów. Zatem iterowanie po liczbach całkowitych od 0 do 2^n minus 1 odwiedza każdy podzbiór dokładnie raz.
for mask in range(1 << n):
pass # mask is one subset1 << n to liczba
Przesunięcie 1 << n jest równe 2 do potęgi n. To przejrzysty i szybki sposób zapisania górnej granicy pętli po podzbiorach.
Odczytywanie bitu i
Aby sprawdzić, czy element i należy do podzbioru, należy przetestować jego bit za pomocą maski i 1 przesuniętej w lewo o i. Wynik różny od zera oznacza, że element należy do podzbioru.
if mask & (1 << i):
take(items[i])Tworzenie listy wybranych elementów
Przejdź po każdej pozycji bitowej i zbierz elementy, których bit jest ustawiony. W ten sposób jedna maska zostaje zamieniona na konkretny podzbiór, który reprezentuje.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Puste i pełne zbiory
Maska 0 oznacza pusty podzbiór, a maska z samymi jedynkami oznacza pełny zbiór. Oba przypadki są uwzględniane automatycznie, ponieważ pętla obejmuje każdą wartość.
Sumowanie podzbioru
Wewnątrz pętli zsumuj wybrane elementy, aby obliczyć wynik dla każdego podzbioru. To podstawa wielu niewielkich rozwiązań typu brute force.
total = sum(v[i] for i in range(n) if mask & (1 << i))Zliczanie ustawionych bitów
Liczba wybranych elementów jest równa wartości popcount maski. W Pythonie wyrażenie bin(mask).count('1') zwraca ją natychmiast.
size = bin(mask).count("1")Uważaj na ograniczenie
Ponieważ istnieje 2^n podzbiorów, ta technika nadaje się tylko dla małych wartości n. W praktyce pełne wyliczanie staje się graniczne przy n równym około 20.
Dlaczego maski bitowe wygrywają
Jedna pętla po liczbach całkowitych zastępuje zawiłe pętle zagnieżdżone, a operacje bitowe są szybkie. Kod pozostaje krótki, przejrzysty i łatwy do przetestowania.
Uniwersalny schemat
Przechodź po maskach, odczytuj ich bity, obliczaj wynik podzbioru i zapamiętuj najlepszy rezultat. Warto zapamiętać ten szablon, ponieważ wiele problemów dotyczących podzbiorów stanie się rutynowych.
Szybkie sprawdzenie
Należy sprawdzić, czy element i należy do podzbioru zakodowanego w masce.
Podsumowanie
Przechodź po maskach od 0 do 2^n minus 1, odczytuj bity za pomocą maski i 1 przesuniętej w lewo, a następnie obliczaj wynik każdego podzbioru. To przejrzysta metoda brute force dla małych wartości n. 🚀
Często zadawane pytania
Czy lekcja „Enumerowanie podzbiorów za pomocą masek bitowych” jest bezpłatna?
Tak — pełny tekst „Enumerowanie podzbiorów za pomocą masek bitowych” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Enumerowanie podzbiorów za pomocą masek bitowych”?
Iterowanie po wszystkich podzbiorach za pomocą liczb całkowitych Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Enumerowanie podzbiorów za pomocą masek bitowych”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Bruteforce to prawidłowa strategia
- Enumerowanie za pomocą itertools
- Enumerowanie podzbiorów za pomocą masek bitowych
- Sprytne zawężanie przestrzeni wyszukiwania