Pytania otagowane jako dynamic-programming

Pytania o problemy, które można rozwiązać, łącząc rekurencyjnie uzyskane rozwiązania podproblemów.

3
Problem z plecakiem - NP-kompletny pomimo dynamicznego rozwiązania programistycznego?
Problemy z plecakiem można łatwo rozwiązać za pomocą programowania dynamicznego. Programowanie dynamiczne przebiega w czasie wielomianowym; dlatego to robimy, prawda? Przeczytałem, że jest to w rzeczywistości problem NP-zupełny, co oznaczałoby, że rozwiązanie problemu wielomianowego jest prawdopodobnie niemożliwe. Gdzie jest mój błąd?
3
Decydowanie o problemach podrzędnych dla programowania dynamicznego
Wielokrotnie korzystałem z techniki programowania dynamicznego, ale dzisiaj mój przyjaciel zapytał mnie, jak zabrać się do definiowania moich pod-problemów, zdałem sobie sprawę, że nie mam możliwości udzielenia obiektywnej formalnej odpowiedzi. Jak formalnie zdefiniować pod-problem dotyczący problemu, który rozwiązalibyście za pomocą programowania dynamicznego?
4
Na czym polega programowanie dynamiczne?
Z góry przepraszam, jeśli to pytanie brzmi głupio ... O ile wiem, budowanie algorytmu przy użyciu programowania dynamicznego działa w ten sposób: wyrazić problem jako relację nawrotu; wdrożyć relację powtarzalności albo poprzez zapamiętywanie, albo poprzez podejście oddolne. O ile wiem, powiedziałem wszystko o programowaniu dynamicznym. Mam na myśli: programowanie dynamiczne …
5
Rozróżnienie przypadków w programowaniu dynamicznym: potrzebny przykład!
Od jakiegoś czasu pracuję nad programowaniem dynamicznym. Kanonicznym sposobem oceny dynamicznej rekurencji programowania jest utworzenie tabeli wszystkich niezbędnych wartości i wypełnienie jej wiersz po wierszu. Zobacz na przykład Cormen, Leiserson i in .: „Wprowadzenie do algorytmów” . Skupiam się na opartym na tabeli schemacie obliczeń w dwóch wymiarach (wypełnianie wiersz …
6
Czym różni się programowanie dynamiczne od siły Brute?
Czytałem o Programowaniu dynamicznym, kiedy natknąłem się na następujący cytat Algorytm programowania dynamicznego zbada wszystkie możliwe sposoby rozwiązania problemu i wybierze najlepsze rozwiązanie. Dlatego z grubsza możemy myśleć o programowaniu dynamicznym jako inteligentnej metodzie brutalnej siły, która pozwala nam przejść przez wszystkie możliwe rozwiązania, aby wybrać najlepsze . Jeśli zakres …
3
Największa suma podzielna przez n
Zadałem to pytanie na StackOverflow , ale myślę, że tutaj jest bardziej odpowiednie miejsce. Jest to problem od kursu Wprowadzenie do algorytmów : Musisz tablicę aaa z liczb całkowitych dodatnich (tablica nie muszą być sortowane lub elementów unikalnych). Zaproponuj algorytm , aby znaleźć największą sumę elementów, która jest podzielna przez …
3
Zapamiętywanie bez tablicy
W Cormen et al .'s Wprowadzenie do algorytmów , sekcja 15.3 Elementy programowania dynamicznego wyjaśniają zapamiętywanie w następujący sposób: Zapamiętany algorytm rekurencyjny zachowuje pozycję w tabeli dla rozwiązania każdego podproblemu. Każdy wpis w tabeli początkowo zawiera specjalną wartość wskazującą, że wpis musi jeszcze zostać wypełniony. Gdy podproblem zostanie napotkany po …
2
Kiedy mogę zastosować programowanie dynamiczne, aby zmniejszyć złożoność czasową mojego algorytmu rekurencyjnego?
Programowanie dynamiczne może skrócić czas potrzebny do wykonania algorytmu rekurencyjnego. Wiem, że programowanie dynamiczne może pomóc w zmniejszeniu złożoności czasowej algorytmów. Czy ogólne warunki są takie, że spełnienie algorytmu rekurencyjnego oznaczałoby, że zastosowanie programowania dynamicznego zmniejszy złożoność czasową algorytmu? Kiedy powinienem używać programowania dynamicznego?
2
Faktoryzacji słowo w Czas
Biorąc pod uwagę dwa ciągi , piszemy dla ich konkatenacji. Biorąc pod uwagę ciąg i liczba całkowita , napisać dla złączonych kopii . Teraz biorąc pod uwagę ciąg, możemy użyć tego zapisu do „skompresowania” go, tzn. można zapisać jako . Nazwijmy ten ciężar kompresji liczba znaków w niej występujących, więc …
1
Wariant problemu plecakowego
Jak podchodziłbyś do problemu plecaka w sytuacji dynamicznego programowania, gdybyś musiał teraz ograniczyć liczbę przedmiotów w plecaku o stałe ppp ? Jest to ten sam problem (maksymalna waga WWW , każdy przedmiot ma wartość vvv i ciężar www ), ale można dodać tylko ppp przedmiotów do plecaka i oczywiście trzeba …
2
Programowanie dynamiczne z dużą liczbą podproblemów
Programowanie dynamiczne z dużą liczbą podproblemów. Więc próbuję rozwiązać ten problem z ulicy wywiadu: Grid Walking (Zdobądź 50 punktów) Znajdujesz się w siatce NNN wymiarowej na pozycji (x1,x2,…,xN)(x1,x2,…,xN)(x_1,x_2,\dots,x_N) . Wymiary siatki to (D1,D2,…,DN(D1,D2,…,DN(D_1,D_2,\dots,D_N ). W jednym kroku możesz przejść jeden krok do przodu lub do tyłu w dowolnym z NNN …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.