w plecaku
Waga
Najlepszy możliwy

    Przedmioty

      Więcej o problemie plecakowym

      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

      1. Stuknij pudełka, aby spakować je do plecaka, i patrz, jak wypełnia się według wagi w kilogramach.
      2. Spróbuj osiągnąć najlepszą możliwą wartość w dolarach albo naciśnij Najlepsze pakowanie, aby zobaczyć najlepszy plecak.
      3. 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