# Dynamic Programming **Group G** 謝皓青．林暘瑾．郭浩雲 --- ## Introduction Dynamic Programming, a technique of breaking down a problem into subproblems, solving these subproblems once, and storing their solutions. ---- ### Key attribute * optimal substructure * overlapping sub-problem ---- ### Optimal substructure Find the shortest path from A to F  ---- ### Optimal substructure The solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems ---- ### Overlapping sub-problem Fibonacci series 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144  ---- ### Overlapping sub-problem If a problem can be divided into subproblems which are reused several times ---- ### Why dynamic programming? ---- recursive way  ---- dynamic programming way  ---- ### Summary *Footprints in the sand show where one has been* 凡走過必留下痕跡 *Use additional memory to save computation time* 用記憶體換速度 > cited from our algorithm Prof. Mei-chien Yeh. --- ### Top-down or bottom-up strategy Different view to the same problem. Same complexity. Further explanation in case study. --- ### Case Study: Knapsack problem  How do you put items into a bag to maximize the total value within a given limit of weight?  ---- #### Brute force Take or not take, that is the question. The most straight forward idea. $2^n$ subsets, $n$ rounds Results in $O(N\cdot 2^n)$ time complexity Extremely inefficient ---- #### Greedy? Take items that have the highest value, and then the less value one, and so on. Sometimes a set of "cheap items" results in higher value than a set of a few "expensive items". No suitable. ---- #### DP  ----  For each element in the table, we compute $T[i,j]=\begin{cases}max(T[i-1,j], T[i-1,j-w_i]+v_i)\\T[i-1,j], \text{if }j-w_i<0\end{cases}$ ----  ---- #### Soloving * unbounded knapsack problem * 0-1 knapsack problem * other problrm  ---- unbounded knapsack problem  ---- 0-1 knapsack problem