## Lecture 02. Problem Solving Paradigms - Part 2
- Greedy
- Dynamic Programming
---
### 3. Greedy
- Always make a choice that looks the **best at the moment**
- Never takes back its choices, but directly constructs the final solution
- The difficulty: find a greedy strategy, in which the locally optimal choices is also the globally optimal
Note:
- Very efficient
- Difficult to argue that a greedy algorithm works (diffcult or not cost-effective to prove during contest)
---
### 3. Greedy
A problem can be solved using a greedy algorithm if:
- It has optimal sub-structures
- It has the greedy property
---
### 3. Greedy: Coin exchange
Given $k$ coins of values $coins = \{c_1, c_2,..., c_k\}$, each has unlimited amount. What is the minimum number of coins needed to make a sum of money $n$.
Ex.: ${1,2,5,10,20,50,100,200}$
$n=520$?
---
### 3. Greedy: Coin exchange
$coins = \{1,2,5,10,20,50,100,200\}$
$n=520$
Greedy: always selects the largest possible coin
→ **It works!**
Note:
- proof? --> not easy
---
### 3. Greedy: Coin exchange
$coins = \{1,3,4\}$
$n=6$
$4+1+1$ vs $3 + 3$
→ Greedy **doesn't work!**
→ **Dynamic programming**
---
### 3. Greedy: Scheduling
Given $n$ events with their starting and ending times, find a schedule that includes as many events as possible.
| event | start time | end time |
| ------| ---------- | -------- |
| A | 1 | 3 |
| B | 2 | 5 |
| C | 3 | 9 |
| D | 6 | 8 |
<img src="https://cdn.ucode.vn/uploads/1/upload/qaRpQLJK.png"/>
---
### 3. Greedy: Scheduling
Greedy algorithm 1: select as **short** events as possible.
<img src="https://cdn.ucode.vn/uploads/1/upload/MITZAiAH.png"/>
---
### 3. Greedy: Scheduling
Greedy algorithm 1: Failed case
<img src="https://cdn.ucode.vn/uploads/1/upload/qiOgwXkv.png"/>
---
### 3. Greedy: Scheduling
Greedy algorithm 2: select as **early** event as possible
<img src="https://cdn.ucode.vn/uploads/1/upload/vJBZhgOd.png"/>
---
### 3. Greedy: Scheduling
Greedy algorithm 2: Failed case
<img src="https://cdn.ucode.vn/uploads/1/upload/XjFiEwnd.png"/>
---
### 3. Greedy: Scheduling
Greedy algorithm 3: select event that **ends** as **early** as possible
<img src="https://cdn.ucode.vn/uploads/1/upload/OWzPDGLA.png"/>
→ **It works!**
---
### 3. Greedy: Dragon heads and knights
There are $n$ dragon heads and $m$ knights. A dragon head with diameter $D$ can be chopped off by a knight with height $H$ if $D \le H$. A knight can only chop off one dragon head. Is it possible to chop off all the dragon heads? If yes, what is the minimum total height of the knights used to chop off the dragons’ heads?
Ex.: $D = \{5, 4\}$; $K = \{7, 8, 4\}$
---
### 3. Greedy: Dragon heads and knights
Greed: for each $D$, always choose the knight with **shortest** $H$ such that **$H \ge D$**.
<img src="https://cdn.ucode.vn/uploads/1/upload/KlTmnLUT.png"/>
---
### 4. Dynamic programming
- Combines the correctness of complete search and the efficiency of greedy algorithms
- Can be applied if the problem can be divided into **overlapping** subproblems that can be solved independently.
- Is primarily used to solve **optimization** problems and **counting** problems.
---
### 4. Dynamic programming: Wedding Shopping
Given different options for $C$ ($\le 20$) different garments (e.g., 3 shirt models, 2 belt models, 4 shoe models,...) and a limited budget $M$ ($\le 200$), we need to buy one model of each garment. What is the maximum amount (not exceeds $M$) of money we can spend? Ex:
```
20 3 # M C
6 4 8 # 3 options for garmets 1
5 10 # 2 options for garmets 2
1 5 3 5 # 4 options for garmets 3
```
---
### Wedding Shopping
Greedy: take the **most expensive** model for each garment which still fits our budget.
```
20 3 # M C
6 4 8 # 3 options for garmets 1
5 10 # 2 options for garmets 2
1 5 3 5 # 4 options for garmets 3
```
Ouput: **$19$** (8 + 10 + 1) → **works!**
If $M = 9$ → no solution → **works!**
---
### Wedding Shopping
Greedy: take the **most expensive** model for each garment which still fits our budget.
$M = 12$
```
12 3 # M C
6 4 8 # 3 options for garmets 1
5 10 # 2 options for garmets 2
1 5 3 5 # 4 options for garmets 3
```
→ no solution → **doesn't work!** (correct output is $12$)
---
### Wedding Shopping
Complete search (recursive backtracking)
- $dp(g, b)$ = the answer for sub-problem that we are dealing with garment $g$ and the remaining budget is $b$.
- First, start with $dp(0, M)$, then try all variants of the first garment option (up to $20$), then for each of this first value, call recursion function for the second garment...
---
### Wedding Shopping
Complete search (recursive backtracking)
- Prune the infeasible solution when $b < 0$.
- Stop the model when last garment has chosen (a solution found).
- From all solutions, choose one with **smallest** remaining $b$.
---
### Wedding Shopping
Complete search (recursive backtracking)
- $dp(g, b) = -\infty$, if $b < 0$
- $dp(g, b) = M - b$, if $g = C$ (last garment)
- $\forall i \in [1..k]$ possible values of current garment g:
$dp(g, b) = max(dp(g+1, b-price[g][i]))$
→ correct, but **TLE**
20 garmets, each has 20 options → $20^{20}$ ~ $10^{26}$ cases.
---
### Wedding Shopping: backtracking
```cpp=
int dp(int g, int money) {
if (money < 0) return -1e9;
if (g == C) return M - money;
int ans = -1;
for (int k = 1; k <= price[g].size(); ++k)
ans = max(ans, dp(g+1, money - price[g][k]));
return ans;
}
```
---
### Wedding Shopping: backtracking
```python=
sys.setrecursionlimit(10000)
def dp(g, money):
if money < 0: return -1e9
if g == C: return M-money
ans = -1
# try each of options of garmet g
for p in price[g]:
ans = max(ans, dp(g + 1, money - p))
return ans
```
---
### Wedding Shopping
Divide and Conquer: not applicable, because the sub-problems are not independent.
---
### 4. Dynamic programming: Wedding Shopping
- This problem has optimal sub-structures
- This problem has overlapping sub-structures (many from $20^{20}$ sub-problems are overlapping)
- → **DP**
---
### 4. Dynamic programming: Wedding Shopping
- How many **distinct** sub-problems (**states**)?
- $dp(g, b)$, $20$ values of $g$, $201$ values of $b$
- → $4020$ distinct sub-problems
---
### 4. Dynamic programming: Wedding Shopping - TOP-DOWN approach
- Same as backtracking
- Use memoization for avoid recalculating $dp(g, b)$ for known values
- C++: use a 2D array memo (`memo[MAX_G][MAX_M]`)
- Python: use built-in memoization (`lru_cache`)
---
### 4. Dynamic programming: TOP-DOWN approach
```cpp=
int dp(int g, int money) {
if (money < 0) return -1e9;
if (g == C) return M-money;
// TOP-DOWN: memoization
if (memo[g][money] != -1) return memo[g][money];
int ans = -1;
for (int k = 1; k <= price[g].size(); ++k)
ans = max(ans, dp(g+1, money-price[g][k]));
return memo[g][money] = ans; // TOP-DOWN: memoize ans
}
```
---
### 4. Dynamic programming: TOP-DOWN approach
```python=
@lru_cache(maxsize=None) # from functools import lru_cache
def dp(g, money):
if money < 0: return -1e9
if g == C: return M-money
ans = -1
for p in price[g]:
# TOP-DOWN: memoize ans
ans = max(ans, dp(g+1, money - p))
return ans
```
---
### 4. Dynamic programming: BOTTOM-UP approach
The "true form" of DP: the "tabular method":
- Define the "states" of the problem, with $N$ params
- Prepare an $N$ dimensional array (DP table), with one entry per state and initialize some cells of the DP table with known initial values (the base cases)
- Determine the cells/states that can be filled next. Repeat this process until the DP table is complete.
Note:
- For the bottom-up DP, this part is usually accomplished through iterations, using loops (more details about this later).
---
### 4. Dynamic programming: BOTTOM-UP approach
- $price = [\{6, 4, 8\}, \{5, 10\}, \{1, 5, 3, 5\}]$, $M = 20$
- Boolean matrix $reachable[g][b]$ of size $C \times (M+1)$, $= True$ if can buy any option of garmet $g$ and remain $b$ money.
---
### 4. Dynamic programming: BOTTOM-UP approach
$price = [\{6, 4, 8\}, \{5, 10\}, \{1, 5, 3, 5\}]$, $M = 20$
<img src="https://cdn.ucode.vn/uploads/1/upload/fLTxmlzx.png"/>
The answer: $reachable[2][1] = 1 \rightarrow M-1 = 19$
---
### 4. Dynamic programming: BOTTOM-UP approach
<img src="https://cdn.ucode.vn/uploads/1/upload/LacjJwar.png"/>
**Optimation**: to compute row $g$, we only need values from the previous row $g - 1 \rightarrow reachable[g][b]$ of size $2 \times (M+1)$ only.
---
### 4. Dynamic programming: BOTTOM-UP approach
```python=
# initial values (base cases), using first garment g = 0
for p in price[0]:
if (M - p >= 0):
reachable[0][M - p] = True
for g in range(1, C): # for each remaining garment
for money in range(0, M):
if (reachable[g-1][money]):
for p in price[g]:
if (money - p >= 0):
reachable[g][money - p] = True
```
---
### 4. Dynamic programming: BOTTOM-UP approach (only 2 rows)
```python=
cur = 1 # we start with this row
for g in range(1, C):garment
reachable[cur] = [False for i in range(M)] # reset row
for money in range(0, M):
if (reachable[1-cur][money]): # check another row
for p in price[g]:
if (money - p >= 0):
reachable[cur][money - p] = True
cur = 1 - cur # IMPORTANT: flip the two rows
```
---
### 4. Dynamic programming: TOP-DOWN vs BOTTOM-UP
TOP-DOWN
- Easier implementation (same as complete search)
- Sometime is faster if there are unnecessary sub-problems (using pruning)
- Normally Slower due to function call overhead
- Cannot use space optimization to reduce space (need full memo array to save states)
---
### 4. Dynamic programming: TOP-DOWN vs BOTTOM-UP
BOTTOM-UP
- Normally faster (no function call overhead)
- Can save memory space with optimization
- More difficult implementation
- Some time is slower: fills the value of all these M states even if many of the states are not necessary
---
### 4. Dynamic programming: Display the solution
1. Store the predecessor information at each state, then backtrack from the optimal final state and follow the optimal transition(s) recorded at each state until we reach one of the base cases
2. For top-down approach, we can add another function $print\_dp(g, b)$ that has the same structure as $dp(g, b)$ except that it uses the values stored in the memo table to reconstruct the solution
Note:
Beside the value of optimal solution (the total money), some problems may require to print the optimal solution (the list of garmet).
1st method: for bottom-up (can apply to top-down also)
2nd method: for top-down only
```cpp=
void print_dp(int g, b) { // void function
if ((g == C) || (b < 0)) return; // similar base cases
for (int k = 1; k <= price[g].size(); ++k) // which model k is opt?
if (dp(g+1, b-price[g][k]) == memo[g][b]) { // this one
printf("%d - ", price[g][k]);
print_dp(g+1, b-price[g][k]); // recurse to this only
break;
}
}
```
---
### 4. Dynamic programming: Coin exchange
- $coins = \{1,3,4\}$, $n=6$
- $f(x) \rightarrow$ the minimum number of coins for a sum $x$.
- $f(10)=3, f(6)=2$
- $f(x)= 1 + min(f(x-1), f(x-3), f(x-4))$
- Base case: $f(0) = 0$
---
### 4. Dynamic programming: Coin exchange
```python=
f[0] = 0
for x in range(1, n+1):
f[x] = float("inf")
for c in coins:
if x - c >= 0:
f[x] = min(f[x], f[x-c]+1)
print(f[n])
```
---
### 4. Dynamic programming: Coin exchange
Display the solution
```python=
trace = [0] * (n + 1)
f[0] = 0
for x in range(1, n+1):
f[x] = float("inf")
for c in coins:
if x - c >= 0 and f[x-c] + 1 < f[x]:
f[x] = f[x-c] + 1
trace[x] = c
print(f[n])
while n > 0:
print(trace[n])
n -= trace[n]
```
---
### 4. Dynamic programming: Coin exchange
Count the solution: $count(x) =$ $count(x-1) + count(x-3) + count(x-4)$
```python=
count[0] = 1
for x in range(1, n+1):
for c in coins:
if x - c >= 0:
count[x] += count[x-c]
print(count(n))
```
---
### 4. Dynamic programming: Longest Increasing Subsequence
Find the longest increasing subsequence in an array
of $n$ elements.
<img src="https://cdn.ucode.vn/uploads/1/upload/tndmTbxl.png"/>
- Complete search: $O(2^n)$
- DP: $O(n^2)$
---
### 4. Dynamic programming: Longest Increasing Subsequence
- $f(k)$ - length of LIS that ends at position $k$.
- $f(k) = max(f(j)) + 1, \forall j < k: a[j] < a[k]$
- $trace[k] = j$
<img src="https://cdn.ucode.vn/uploads/1/upload/tndmTbxl.png"/>
- $f = [1, 1, 2, 1, 3, 2, 4, 2]$
- $trace = [-1, -1, 1, -1, 2, 3, 4, 3]$
- Result: $max(f) = 4$
---
### 4. Dynamic programming: 0-1 Knapsack
- Given $n (n \le 1000)$ items, each with value $V_i$ and weight $W_i$, and a maximum knapsack size $S (S \le 10\,000)$, compute the maximum value of the items that we can carry.
- Ex, $n = 4$, $V = \{100, 70, 50, 10\}$, $W = \{10, 4, 6, 12\}$, $S = 12$
- $\rightarrow$ take item $1$ and $2$ ($0$-based index)
---
### 4. Dynamic programming: 0-1 Knapsack
- $dp(i, w) \rightarrow$ maximum value when considering current $i$ item and remaining weight left is $w$
- $dp(i, w) =$ $max(dp(i+1, w), V_i + dp(i+1, w - W_i))$
- $O(nS)$
---
### 4. Dynamic programming: 0-1 Knapsack
```python=
@lru_cache(maxsize=None)
dp(i, w):
if i == N or w == 0: return 0; # two base cases
# no choice, skip
if (W[i] > w) return ans = dp(id + 1, remW);
return max(dp(i + 1, w), # skip
V[i] + dp(i + 1, w-W[i])); # or take
}
dp(0, S)
```
Note:
The top-down version of this DP solution is often faster than the bottom-up
version. This is because not all states are actually visited, and hence the critical DP states involved are actually only a (very small) subset of the entire state space. Remember that the top-down DP only visits the required states whereas the bottom-up DP visits all distinct states. Both versions are provided in our source code library
---
## The End
---
{"metaMigratedAt":"2023-06-17T19:46:06.687Z","metaMigratedFrom":"YAML","title":"Thuc Nguyen's ADSA Course - Lecture 02. Problem Solving Paradigms - P2","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":16655,\"del\":1955}]"}