Maskowanie bitów
Lekcja 13 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.
Maskowanie bitowe to technika stosowana w programowaniu dynamicznym do optymalizacji rozwiązań obejmujących podzbiory lub kombinacje elementów. Polega na reprezentowaniu każdego podzbioru lub kombinacji jako maski bitowej, w której każdy bit oznacza obecność lub brak odpowiadającego mu elementu. Dzięki operacjom na bitach algorytmy programowania dynamicznego mogą efektywnie iterować po wszystkich możliwych podzbiorach lub kombinacjach bez ich jawnego generowania.
Wyzwanie
TrudnyPolicz podzbiory o danej sumie
W tym wyzwaniu otrzymujesz tablicę liczb całkowitych oraz docelową sumę. Twoim zadaniem jest znalezienie liczby podzbiorów tablicy, których suma jest równa docelowej sumie. Możesz użyć maskowania bitowego, aby przeiterować po wszystkich możliwych podzbiorach tablicy i policzyć te, których suma jest równa docelowej sumie.
Spróbuj swoich sił
def count_subsets(arr, target_sum):
# Wpisz tutaj kodWszystkie lekcje w sekcji Programowanie dynamiczne — podstawy
1Wprowadzenie do programowania dynamicznego
Czym jest programowanie dynamiczne?Dlaczego jest ważne?Zastosowania w różnych dziedzinach4Zaawansowane zagadnienia
Minimalna długość podtablicyPrzycinanieOptymalizacja pamięciMaskowanie bitów3Algorytmy programowania dynamicznego
Najdłuższy wspólny podciągProblem plecakowyProblem wydawania resztyOdległość edycyjnaPoćwicz samodzielnie: Kompilator Python online