Mascheramento dei bit
Lezione 13 di 15 del corso Programmazione dinamica 101 di Coddy.
Il mascheramento dei bit è una tecnica usata nella programmazione dinamica per ottimizzare le soluzioni che coinvolgono sottoinsiemi o combinazioni di elementi. Consiste nel rappresentare ogni sottoinsieme o combinazione come una maschera di bit, in cui ogni bit della maschera rappresenta la presenza o l'assenza dell'elemento corrispondente. Usando operazioni di manipolazione dei bit, gli algoritmi di programmazione dinamica possono iterare in modo efficiente su tutti i possibili sottoinsiemi o combinazioni senza generarli esplicitamente.
Sfida
DifficileConta i sottoinsiemi con una somma data
In questa sfida, ti viene fornito un array di numeri interi e una somma obiettivo. Il tuo compito è trovare il numero di sottoinsiemi dell'array la cui somma è pari alla somma obiettivo. Puoi usare le maschere di bit per iterare su tutti i possibili sottoinsiemi dell'array e contare quanti hanno una somma pari alla somma obiettivo.
Provalo tu
def count_subsets(arr, target_sum):
# Scrivi il codice quiTutte le lezioni di Programmazione dinamica 101
1Introduzione alla DP
Che cos’è la programmazione dinamica?Perché è importante?Applicazioni in vari campi4Argomenti avanzati
lunghezza_minima_sottoarrayPotaturaOttimizzazione dello spazioMascheramento dei bit3Algoritmi di programmazione dinamica
Sottosequenza comune più lungaProblema dello zainoProblema del cambio delle moneteDistanza di modificaEsercitati da solo: Compilatore Python online