Plecak bez ograniczeń i DP wydawania reszty
Używanie elementów dowolną liczbę razy
Plecak bez ograniczeń i DP wydawania reszty 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.
Nieograniczona liczba przedmiotów
W problemie plecakowym bez ograniczeń każdy przedmiot można zabrać dowolnie wiele razy. Należy myśleć o monetach w automacie, a nie o stałym stosie przedmiotów.
Jedna drobna zmiana
W porównaniu z wariantem 0/1 zmienia się tylko kierunek pętli. Dla przedmiotów bez ograniczeń pojemność należy przetwarzać wprzód, od małej do dużej.
Ponowne użycie w przód jest sednem
Przechodzenie w przód sprawia, że dp[w - coin] może już uwzględniać ten sam przedmiot. To zamierzone ponowne użycie pozwala zabrać go ponownie.
Poznaj problem wydawania reszty
Klasyczny problem wydawania reszty polega na znalezieniu najmniejszej liczby monet, których suma daje określoną kwotę. To DP bez ograniczeń, w którym zamiast maksimum wybiera się minimum.
Zdefiniuj stan
Niech dp[a] oznacza najmniejszą liczbę monet potrzebnych do uzyskania kwoty a. Należy zacząć od dp[0] = 0, ponieważ do uzyskania zera nie potrzeba żadnych monet.
dp = [float("inf")] * (amount + 1)
dp[0] = 0Użyj nieskończoności dla przypadków niemożliwych
Nieosiągalne kwoty należy początkowo oznaczyć jako nieskończoność. Jeśli na końcu kwota nadal ma wartość nieskończoną, nie da się jej uzyskać za pomocą żadnej kombinacji monet.
Przejście
Dla każdej monety należy spróbować poprawić wynik dla każdej kwoty, którą można nią uzyskać. Trzeba użyć o jedną monetę więcej niż w przypadku najlepszego rozwiązania dla pozostałej mniejszej kwoty.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Dlaczego kolejność w przód
Przetwarzanie kwot rosnąco pozwala, aby dp[a - coin] już uwzględniało tę monetę. Dzięki temu jedna moneta może zostać użyta wielokrotnie.
Zamiast tego zlicz sposoby
Zamiast min+1 należy użyć sumy, aby policzyć liczbę sposobów uzyskania każdej kwoty. Pętla po monetach na zewnątrz zapobiega podwójnemu zliczaniu kolejności.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Odczytaj wynik
Wynik znajduje się w dp[amount]. W wariancie minimalnym wartość nieskończona oznacza, że nie można uzyskać docelowej kwoty.
0/1 a plecak bez ograniczeń
Należy zapamiętać jedną zasadę: przetwarzanie pojemności wstecz oznacza użycie każdego przedmiotu raz, a w przód — użycie go dowolnie wiele razy. Ta sama tabela, lecz przeciwne kierunki przejścia.
Szybkie sprawdzenie
Sprawdź, co sprawia, że problem plecakowy jest nieograniczony.
Podsumowanie
Odwrócili Państwo kierunek pętli na wprzód, aby umożliwić nieograniczone ponowne użycie, i zbudowali problem wydawania reszty: z minimum dla najmniejszej liczby monet albo z sumą dla łącznej liczby sposobów. 💰
Często zadawane pytania
Czy lekcja „Plecak bez ograniczeń i DP wydawania reszty” jest bezpłatna?
Tak — pełny tekst „Plecak bez ograniczeń i DP wydawania reszty” 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 „Plecak bez ograniczeń i DP wydawania reszty”?
Używanie elementów dowolną liczbę razy Ć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 „Plecak bez ograniczeń i DP wydawania reszty”?
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
- Plecak 0/1: wziąć czy zostawić
- Plecak ze zoptymalizowanym zużyciem pamięci
- Plecak bez ograniczeń i DP wydawania reszty
- Suma podzbioru i podział