Plecak ułamkowy według ilorazu
Wybieranie najpierw najwyższej wartości na jednostkę wagi
Plecak ułamkowy według ilorazu 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.
Konfiguracja problemu plecakowego
Do dyspozycji są przedmioty o określonej wartości i wadze oraz plecak o ograniczonej pojemności. Celem jest zabranie możliwie największej łącznej wartości. 🎒
Wersja ułamkowa pozwala dzielić
W wersji ułamkowej można zabrać część przedmiotu, na przykład połowę worka zboża. To właśnie ta swoboda pozwala algorytmowi zachłannemu znaleźć rozwiązanie.
Wartość na jednostkę wagi
Kluczową miarą jest stosunek wartości przedmiotu do jego wagi. Wysoki stosunek oznacza dużą wartość upakowaną na bardzo małej przestrzeni.
ratio = value / weightSortowanie według najlepszego stosunku
Należy posortować przedmioty według wartości na jednostkę wagi, od najwyższej do najniższej. Strategia zachłanna polega na wybieraniu przedmiotów o największej dostępnej gęstości wartości.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Zabieranie całych przedmiotów, dopóki się mieszczą
Należy przejść po posortowanej liście i zabrać każdy przedmiot w całości, jeśli mieści się jeszcze w pozostałej pojemności. Do sumy należy dodać jego pełną wartość.
if weight <= cap:
total += value
cap -= weightWypełnienie ostatniej luki
Gdy przedmiot jest zbyt duży, należy zabrać taki ułamek, który dokładnie wypełni pozostałe miejsce. Plecak będzie wtedy pełny i można zakończyć działanie.
total += value * (cap / weight)Dlaczego działa kolejność według stosunku
Każda jednostka pojemności powinna zawierać możliwie największą wartość, dlatego przedmiot o największej gęstości musi zostać wybrany pierwszy. Zastąpienie go przedmiotem o mniejszej gęstości tylko zmniejsza wartość.
Problem plecaka 0/1 jest inny
Jeśli przedmiotów nie można dzielić, zachłanny wybór według stosunku wartości do wagi zawodzi. Wersja 0/1 wymaga programowania dynamicznego, a nie prostego sortowania.
Czas działania
Sortowanie według stosunku wartości do wagi kosztuje O(n log n), a pętla wypełniająca plecak działa liniowo. To wystarczająco szybko dla typowych limitów zadań konkursowych.
Uważaj na końcowy ułamek
Do częściowego przedmiotu użyj arytmetyki zmiennoprzecinkowej albo dokładnych liczb wymiernych. Zbyt wczesne obcinanie wartości może ją zmniejszyć i doprowadzić do błędnej odpowiedzi.
Gdzie to się przydaje
Pomyśl o ładowaniu ładunku, mieszaniu paliw albo dzieleniu zasobów. Gdy tylko przedmioty można dzielić, algorytm zachłanny oparty na stosunku wartości do wagi jest właściwym narzędziem.
Szybkie sprawdzenie
Wypełnia Pan/Pani plecak w problemie plecaka ułamkowego.
Podsumowanie
Posortuj przedmioty według wartości przypadającej na jednostkę wagi, bierz całe przedmioty, dopóki się mieszczą, a następnie dopełnij plecak ułamkiem kolejnego przedmiotu. Ten algorytm zachłanny jest optymalny tylko wtedy, gdy przedmioty można dzielić. 🚀
Często zadawane pytania
Czy lekcja „Plecak ułamkowy według ilorazu” jest bezpłatna?
Tak — pełny tekst „Plecak ułamkowy według ilorazu” 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 ułamkowy według ilorazu”?
Wybieranie najpierw najwyższej wartości na jednostkę wagi Ć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 ułamkowy według ilorazu”?
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
- Sposób myślenia zachłannego
- Wybór aktywności według najwcześniejszego zakończenia
- Plecak ułamkowy według ilorazu
- Rozpoznawanie, kiedy zachłanność zawodzi