- Wypełniana
- Odczytywana
- Odpowiedź
Problem plecakowy
Możesz unieść tylko określoną wagę, a każdy przedmiot ma wagę i wartość. Które przedmioty zabrać, aby nieść jak największą wartość? Sprawdzanie każdej kombinacji podwaja pracę z każdym przedmiotem. Tabela z wierszami przedmiotów i kolumnami pojemności znajduje najlepszy plecak komórka po komórce. Stuknij przedmiot, aby włożyć go do plecaka, i stuknij go ponownie (w plecaku lub na półce), aby go wyjąć. Plecak zapełnia się według wagi, a kafelki pokazują spakowane dolary w porównaniu z najlepszym możliwym wynikiem. Naciśnij Najlepsze pakowanie, aby zobaczyć najlepszy plecak. W panelu zmieniaj kilogramy i dolary przedmiotów, dodawaj lub usuwaj przedmioty i ustaw pojemność plecaka. Widok Tabela pokazuje, jak programowanie dynamiczne znajduje najlepszy plecak: naciśnij Odtwórz, aby zobaczyć, jak tabela się wypełnia, albo Krok i Wstecz, aby przechodzić krok po kroku, i przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Każdy wiersz dodaje jeden przedmiot, każda kolumna to pojemność w kilogramach, a każda komórka zawiera najwięcej dolarów, ile się zmieści. Gdy tabela jest zaznaczona, klawisze strzałek przechodzą o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.
Jak to działa
- Stuknij pudełka, aby spakować je do plecaka, i patrz, jak wypełnia się według wagi w kilogramach.
- Spróbuj osiągnąć najlepszą możliwą wartość w dolarach albo naciśnij Najlepsze pakowanie, aby zobaczyć najlepszy plecak.
- Otwórz widok Tabela i naciśnij Odtwórz, aby zobaczyć, jak każda komórka wybiera między spakowaniem a pominięciem przedmiotu.
Jak działa tabela
Każdy wiersz dodaje jeden przedmiot, a każda kolumna to pojemność od 0 do pojemności plecaka. Komórka zawiera największą wartość, która mieści się w tej pojemności przy użyciu przedmiotów do jej wiersza. Bez nowego przedmiotu jest to komórka powyżej. Z nim, jeśli się mieści, jest to wartość przedmiotu plus najlepsza wartość dla pozostałej wagi, która znajduje się w wierszu powyżej, o wagę przedmiotu w lewo. Komórka zachowuje większą z tych dwóch wartości. Pierwszy wiersz, bez przedmiotów, to same zera.
Odczytywanie przedmiotów wstecz
Prawa dolna komórka to najlepsza wartość. Aby znaleźć przedmioty, zacznij od niej i porównaj ją z komórką powyżej: jeśli jest taka sama, ostatni przedmiot nie był potrzebny; jeśli jest większa, przedmiot jest w plecaku, więc odejmij jego wagę i przejdź do tej kolumny. Za każdym razem przejdź o wiersz w górę, aż do pierwszego wiersza. Aplikacja pokazuje ten odczyt na pomarańczowo i wypisuje spakowane przedmioty pod tabelą.
Często zadawane pytania
Co oznacza 0/1 w problemie plecakowym 0/1?
Każdy przedmiot pakuje się raz albo wcale, nigdy częściowo i nigdy dwa razy. Gdyby przedmioty można było dzielić, jak ziarnka ryżu, pakowanie najpierw najlepszej wartości na jednostkę wagi byłoby optymalne; to jest ciągły problem plecakowy.
Dlaczego nie pakować najpierw najlepszej wartości na jednostkę wagi?
Bo całe przedmioty mogą zostawiać luki. Przy pojemności 7 i przedmiotach o wagach 1, 3, 4 i 5 oraz wartościach 1, 4, 5 i 7 najlepszą wartość na jednostkę wagi ma przedmiot o wadze 5, który zostawia miejsce tylko na przedmiot o wadze 1, razem 8. Przedmioty o wagach 3 i 4 są razem warte 9.
Jak szybki jest algorytm plecakowy?
Tabela ma (liczba przedmiotów + 1) razy (pojemność + 1) komórek, a każdą wypełnia się w jednym kroku. To szybkie dla małych pojemności, ale pojemność może być ogromną liczbą, więc w ogólności problem jest NP-trudny; metodę tabeli nazywa się pseudowielomianową.
Czy ten sam przedmiot można spakować dwa razy?
Nie tutaj. W nieograniczonym problemie plecakowym każdy przedmiot można wziąć dowolną liczbę razy; tabela odczytuje wtedy komórkę po lewej w tym samym wierszu zamiast wiersza powyżej, jak w aplikacji o wydawaniu reszty.
Czy cokolwiek jest gdzieś wysyłane?
Nie. Wszystko jest obliczane w twojej przeglądarce, a twoje ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora