Załóżmy, że jesteś złodziejem i zaatakowałeś dom. W środku znalazłeś następujące przedmioty:Drukowanie Przedmioty znajdujące się w worku w plecaku
Wazon, który waży 3 funty i jest wart 50 dolarów.
Srebrzysty samorodek, który waży 6 funtów i jest wart 30 dolarów.
Obraz, który waży 4 funty i jest wart 40 dolarów.
Lustro, które waży 5 funtów i jest warte 10 dolarów.
Rozwiązanie tego problemu z plecakiem o wadze 10 funtów to 90 dolarów.
stołowy wykonany z programowania dynamicznego jest: -
Teraz chcę wiedzieć, które elementy i umieścić w worku za pomocą tej tabeli to jak BackTrack ??
Hej możesz dać mi jakiś wewnętrzny pomysł, aby uzyskać więcej uczuć na temat tego algo. –
@ T.J Musisz być bardziej szczegółowy o tym, co chcesz wyjaśnić lepiej. Rekursja działa w ten sposób: jeśli 'f [i] [w] <= f [i-1] [w]', to nie potrzebujemy elementu i, więc po prostu powracamy do podzbioru '1..- 1'. Jeśli 'f [i] [w]> f [i-1] [w]', musimy użyć elementu i, aby osiągnąć optymalny wynik, więc pakujemy go do torby. Pozostała torba ma pojemność "w-wagi elementu i" i chcemy spakować jak najwięcej elementów "1..i-1" do tej pozostałej pojemności –
Myślę, że pomysł ten można również określić w następujący sposób. Pod koniec programowania dynamicznego wybiera się optymalny stan, aby uzyskać optymalną wartość. Cofanie jest wykorzystywane do ustalenia, który stan "poprzedni", tj. Stanu, na podstawie którego wygenerowano stan optymalny. Cofanie jest następnie iterowane w tym poprzednim stanie, aż zostanie znaleziony stan początkowy (to znaczy pusty plecak). Uważam to za dość wnikliwe, ponieważ od kilku lat uważałem, że konieczne jest zachowanie jakiejś struktury pomocniczej, która odnosiłaby się do odpowiedniego stanu poprzedniego podczas generowania przestrzeni państwowej. – Codor