Enumerazione dei sottoinsiemi con bitmask
Iterare tutti i sottoinsiemi tramite interi
Enumerazione dei sottoinsiemi con bitmask è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
I sottoinsiemi come numeri
Ogni sottoinsieme di n elementi corrisponde a un unico intero. Conti da 0 in su: i bit di ogni numero indicano esattamente quali elementi sono inclusi. 🙂
Quanti sottoinsiemi
Un insieme di n elementi ha 2^n sottoinsiemi. Quindi, facendo variare un intero da 0 a 2^n meno 1, si visita ogni sottoinsieme esattamente una volta.
for mask in range(1 << n):
pass # mask is one subset1 << n è il numero
Lo shift 1 << n equivale a 2 elevato alla potenza n. È il modo più chiaro e rapido per scrivere il limite superiore del ciclo sui sottoinsiemi.
Leggere il bit i
Per verificare se l'elemento i appartiene al sottoinsieme, controlli il suo bit usando una maschera e 1 spostato a sinistra di i. Un risultato diverso da zero significa che l'elemento è incluso.
if mask & (1 << i):
take(items[i])Creare la lista degli elementi scelti
Esamini ogni posizione di bit e raccolga gli elementi il cui bit è impostato. In questo modo una maschera viene trasformata nel sottoinsieme concreto che rappresenta.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Insiemi vuoti e completi
La maschera 0 rappresenta il sottoinsieme vuoto, mentre la maschera con tutti i bit a 1 rappresenta l'insieme completo. Entrambi vengono inclusi automaticamente, perché il ciclo copre ogni valore.
Sommare su un sottoinsieme
All'interno del ciclo, sommi gli elementi scelti per assegnare un punteggio a ogni sottoinsieme. Questo è il cuore di molte soluzioni di brute force semplici.
total = sum(v[i] for i in range(n) if mask & (1 << i))Contare i bit impostati
Il numero di elementi scelti equivale al popcount della maschera. In Python, bin(mask).count('1') lo restituisce immediatamente.
size = bin(mask).count("1")Attenzione al limite
Poiché esistono 2^n sottoinsiemi, questa tecnica è adatta solo a valori piccoli di n. Un valore intorno a n uguale a 20 è il limite pratico per un'enumerazione completa.
Perché vincono le maschere di bit
Un solo ciclo su un intero sostituisce complicati cicli annidati, e le operazioni sui bit sono veloci. Il codice resta breve, chiaro e facile da testare.
Uno schema riutilizzabile
Esegua il ciclo sulla maschera, decodifichi i suoi bit, calcoli il punteggio del sottoinsieme e tenga traccia del migliore. Memorizzi questo modello e molti problemi sui sottoinsiemi diventeranno esercizi di routine.
Verifica rapida
Vuole verificare se l'elemento i è incluso nel sottoinsieme codificato dalla maschera.
Riepilogo
Esegua un ciclo su una maschera da 0 a 2^n meno 1, legga i bit usando la maschera e 1 spostato a sinistra, quindi calcoli il punteggio di ogni sottoinsieme. È una soluzione di brute force chiara per valori piccoli di n. 🚀
Domande Frequenti
La lezione «Enumerazione dei sottoinsiemi con bitmask» è gratuita?
Sì — il testo completo di «Enumerazione dei sottoinsiemi con bitmask» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Enumerazione dei sottoinsiemi con bitmask»?
Iterare tutti i sottoinsiemi tramite interi Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Enumerazione dei sottoinsiemi con bitmask»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- La forza bruta è una strategia valida
- Enumerare con itertools
- Enumerazione dei sottoinsiemi con bitmask
- Ridurre con criterio lo spazio di ricerca