Programowanie dynamiczne to technika programowania, która polega na dzieleniu problemu na mniejsze podproblemy, szukaniu dla nich rozwiązania, a następnie zapamiętywania znalezionego rozwiązania, by je ponownie wykorzystać.

Istotnym aspektem programowania dynamicznego jest zasada optymalności Bellmana. Zgodnie z nią optymalne rozwiązanie problemu można skonstruować z optymalnych rozwiązań jego podproblemów. Innymi słowy, jeśli mamy do czynienia z procesem decyzyjnym rozłożonym w czasie, to strategia, która jest optymalna dla całego procesu, musi być również optymalna dla każdego etapu procesu.

Zapewne dostrzegasz już podobieństwo do poznanej już techniki dziel i zwyciężajPv0IXD75Rdziel i zwyciężaj – więcej na ich temat znajdziesz w sekcji „Przeczytaj”.

W tym e‑materiale wykorzystamy programowanie dynamiczne, by rozwiązać problem plecakowy, który szerzej omawiamy w serii e‑materiałów mu poświęconych.

Implementację rozwiązań wykorzystujących programowanie dynamiczne w wybranych językach programowania znajdziesz w e‑materiałach:

• Programowanie dynamiczne dla problemu plecakowego w języku C++PfMBkTgnGProgramowanie dynamiczne dla problemu plecakowego w języku C++,

• Programowanie dynamiczne dla problemu plecakowego w języku JavaP1B4u46WqProgramowanie dynamiczne dla problemu plecakowego w języku Java,

• Programowanie dynamiczne dla problemu plecakowego w języku PythonPz3NUl65zProgramowanie dynamiczne dla problemu plecakowego w języku Python.

Więcej zadań? Przejdź do: Programowanie dynamiczne dla problemu plecakowego – zadania maturalneP3uZwGn7mProgramowanie dynamiczne dla problemu plecakowego – zadania maturalne.

Jeśli chcesz powtórzyć wiadomości dotyczące samego problemu plecakowego, wróć do odpowiednich e‑materiałów:

• Problem plecakowyP1G01KROiProblem plecakowy,

• Problem plecakowy w języku C++PZG7khrclProblem plecakowy w języku C++,

• Problem plecakowy w języku JavaP17vy00swProblem plecakowy w języku Java,

• Problem plecakowy w języku PythonPBdZ2NqknProblem plecakowy w języku Python,

• Problem plecakowy – zadania maturalnePcwpqOfwlProblem plecakowy – zadania maturalne.