---

type: slide
slideOptions:
transition: 'convex'
---

# 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