---
tags: 成大高階競技程式設計 2021
---
# 2021 Week7 - Dynamic Programming
註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。
---
# 動態規劃（Dynamic Programming）
> 動態規劃可視為分治法的延伸
回到費氏數列（Fibonacci sequence），用分治法求解的話：
```cpp!
long long Fib(int n) {
if (n <= 1) return n;
return Fib(n - 1) + Fib(n - 2);
}
```
$Fib(n)$ 被求解 $1$ 次；$Fib(n-1)$ 被求解 $1$ 次；$Fib(n-2)$ 被求解 $2$ 次。
不難看出這又是另一個費氏數列，而總計算量大約為前 $n$ 項的總和。
<hr class="thin">
這麼多子問題被重複求解，我們可以透過記憶化（[Memoization](https://en.wikipedia.org/wiki/Memoization)）來避免，
這就是動態規劃的想法。
```cpp!
const int maxn{90};
vector<int> F(maxn + 1, 0);
long long Fib(int n) {
if (n <= 1) return n;
if (F[n]) return F[n];
// memoization
return F[n] = Fib(n - 1) + Fib(n - 2);
}
```
這種作法（approach）叫做 **top-down with memoization**。
<hr class="dashed">
## 動態規劃問題的特性
那到底什麼樣的問題適用動態規劃呢？有兩個要素：
第一個是**最佳子結構（optimal substructure）**，最佳解能夠由子問題的最佳解構成；
分治與貪心法同樣有著這個特性。
> A problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.[^optss]
第二個是**重疊子問題（overlapping subproblem）**，這也是為什麼我們使用動態規劃而非分治。
> A problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.[^olsp]
<hr class="dotted">
因為動態規劃的問題有著重疊子問題，並且大多時候都清楚地知道有哪些子問題。
例如要計算 $F(n)$ 的話，$F(0),...,F(n-1)$ 這些子問題都是必需的，
而我們所需要的也就只有這些子問題而已。
```cpp!
long long Fib(int n) {
vector<long long> F(n + 1); // tabulation
F[0] = 0, F[1] = 1;
for (int i{2}; i <= n; ++i) F[i] = F[i - 1] + F[i - 2];
return F[n];
}
```
這種作法叫做 **bottom-up with tabulation**。
> 計算任一問題時，其子問題都應該已經計算完畢。
大多動態規劃都採取第二種做法，除了較**容易計算複雜度**；
也因為子問題依照一定的順序求解，通常可以進行空間優化。
> 像費氏數列只有一層迴圈，時間複雜度就是 $O(n)$；
> 最多只會用到 `F[i - 2]`，所以只需保留三個變數即可，空間複雜度可優化為 $O(1)$。
<hr class="thin">
分治的精神是分而治之；
**動態規劃的精神則主要是從最基本的子問題，
一步一步遞推求解，最終得到原問題的答案。**
> 動態規劃的題目，通常會定義另一個問題 $P(i,j,\dots)$，
> 而一個狀態（state），就是指帶有一組特定的參數 $s=(a,b,\dots)$ 的問題 $P(s)$，
> $dp[s]$ 則是此問題的最佳解；
> 「狀態轉移」，是透過不同狀態之間的關係，使得最佳解能夠進行轉移。
>
> 如何定義一個問題，將影響到狀態之間是否能夠轉移，以及計算複雜度，
> 因此**定義一個好的問題是動態規劃的關鍵所在**。
<hr class="dashed">
## 單源最短路徑（Single-source shortest path）
:::info
給定一個有向圖，$w(u, v)$ 代表有向邊 $(u,v)$ 的權重，
求一個起點到所有點的最短路徑。
:::
先求另一個比較簡單的問題，單點對最短路徑（Single-pair shortest path）。
> 令 $sp(S,X)$ 為 $S\to X$ 的最短距離。
```graphviz
digraph {
S -> A;
S -> B;
A -> B;
A -> D;
B -> C;
C -> D;
C -> E;
}
```
以 $sp(S,D)$ 為例，假設 $S\to D$ 的最短路徑中，
$D$ 的前一點是 $A$，那最短距離就是 $sp(S,A)+w(A,D)$；
但是我們不知道 $D$ 的前一點會是誰，所以也要考慮 $sp(S,C)+w(C,D)$；
$sp(S,A)$ 只有一種可能，也就是 $w(S,A)$；
$sp(S,C)$ 也只有一種可能，就是 $sp(S,B)+w(B,C)$；
$sp(S,B)$ 又有兩種可能了，$w(S,B)$ 或是 $sp(S,A)+w(A,B)=w(S,A)+w(A,B)$；
最後就可以求出 $sp(S,D)$。
回到原本的問題，要找起點到所有點的最短距離，
就每一個點都計算一次就可以了。
```cpp!
// 定義一個足夠大的數字（注意整數溢位），代表不能到達
const int INF{100000};
// 紀錄入邊（incoming edge）
vector<vector<pair<int, int>>> adj{};
vector<optional<int>> d{};
int sp(int v) {
if (d[v]) return d[v].value();
d[v] = INF; // 有可能 adj[v].empty() 為 true
for (auto& [u, w] : adj[v])
d[v] = min(d[v].value(), sp(u) + w);
return d[v].value();
}
int sssp(int s) {
d.assign(adj.size(), nullopt);
d[s] = 0;
for (int v{0}; v < adj.size(); ++v) sp(v);
}
```
> 這邊透過 top-down 的方式求解，因為 buttom-up 不易找出順序，
> 在每個父問題前先求解子問題。（其實可以按照拓樸排序）
先來分析複雜度，每個遞迴函數呼叫都可以「先」視為常數時間，
因為除了第一次呼叫，其餘都只需要回傳之前記憶下來的答案，
剩下的就是考慮所有子問題第一次呼叫時的計算量。
> 這邊給出一種分析 top-down 複雜度的想法，
> 大致可以用下面的公式表達。
**複雜度$=$子問題數量$\times$每個子問題的計算量$=\sum$子問題的計算量**
這題有 $n$ 個子問題，每個子問題的計算量為入邊邊數，
> 不要忘了考慮每個子問題的計算量時，遞迴呼叫皆視為 $O(1)$。
加起來就是 $O(|V|+|E|)$。
<hr class="dotted">
有讀者應該已經發現，上面的舉例其實是一個有向無環圖（DAG），
那如果圖有環呢？
> 不考慮負環（negative cycle）。
```graphviz
digraph {
S -> A;
S -> B;
A -> B;
A -> D;
B -> C;
B -> A;
C -> D;
C -> E;
}
```
在求解 $sp(S,A)$ 時，需要考慮 $sp(S,B)$；
而要計算 $sp(S,B)$ 時，又要考慮 $sp(S,A)$，
這邊就是一個死結。
> 還記得前面說的最佳子結構嗎？
> 既然父問題的最佳解可以透過子問題的最佳解構成，
> 言下之意就是子問題的最佳解要能夠先得到，
> 自然也就不能再反過來依賴父問題的最佳解。
**任何可以透過動態規劃求解的問題，
將所有的子問題的關係化為一個關係圖後，
都應該是一個 DAG，而子問題的求解順序就是一個拓樸排序。**
要注意的是，這邊說的問題是我們定義的問題，而非原問題，
像是 $sp(S,X)$ 在非 DAG 的圖中，無法透過動態規劃求解，
不代表單源最短路徑這個問題沒有動態規劃的解法。
> 這邊因為我們定義的 $sp(S,X)$ 剛好可以與點 $X$ 一一對應，
> 請不要將子問題轉化的關係圖，與題目給定的圖搞混了。
後面會介紹到的最短路徑演算法 [Bellman–Ford algorithm](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Graph2#Bellman-Ford-algorithm)，
實際上就是利用類似的想法，只不過定義了一個不一樣的問題。
<hr class="dashed">
## 背包問題（Knapsack problem）
### 0-1 背包問題（0-1 knapsack problem）
:::info
現在有 $n$ 個物品，每個物品只有一個，價值為 $v_i$，重量為 $w_i$；
現在有一個背包，可以容納重量不超過 $W$ 的物品，
而每個物品只能選擇拿或不拿，最多可以放入多少價值的東西？
:::
> 如果定義的問題只跟重量限制有關的話，是不足夠的，
> 因為沒有任何關於特定物品的資訊，也就沒辦法進行狀態轉移。
定義 $dp[i][j]$ 為考慮前 $i$ 項物品，並且重量限制為 $j$ 時，所能達到的最大價值；
從第 $i$ 個物品的觀點，最佳解就只有拿與不拿兩種情況，而其餘部分，
只需要考慮前 $i-1$ 項物品，所以我們就可以將問題縮小，改為求解子問題，
也就是 $dp[i-1]$ 的部分。
如果不拿第 $i$ 項物品，可以達到的最大價值就是 $dp[i-1][j]$；
如果拿了第 $i$ 項物品，可以達到的最大價值則為 $v_i+dp[i-1][j-w_i]$。
:::success
$dp[i][j] = \max(dp[i-1][j],\ v_i+dp[i-1][j-w_i])$
:::
```cpp!
int O1_knapsack_problem() {
int n, W;
cin >> n >> W;
vector<int> w(n), v(n);
for (int i{0}; i < n; ++i) cin >> w[i] >> v[i];
vector<vector<int>> dp(n, vector<int>(W + 1, 0));
// 只考慮第 0 項
for (int j{w[0]}; j <= W; ++j) dp[0][j] = v[0];
for (int i{1}; i < n; ++i)
for (int j{0}; j <= W; ++j)
if (w[i] > j) dp[i][j] = dp[i - 1][j]; // 物品重量大於重量限制
else dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
return dp[n - 1][W];
}
```
複雜度為 $O(nW)$。
> 這題比較特別，buttom-up 會多計算了一些狀態，
> top-down 的實作留給讀者，這邊來分析一下 top-down 的複雜度，
> 從 $dp[n-1]$ 開始，到 $dp[n-2],dp[n-3],...$，
> 每層需要計算的狀態最多會變為 $2$ 倍，增加的速度通常很快，
> 最後被 $2W$ 限制住，複雜度還是 $O(nW)$。
>
> 除非物品的重量 $w_i$ 重複性很高，才會導致每層需要計算的狀態很少，
> 最極端的情況，每個物品重量都一樣的話，$dp[n-1-k]$ 只有 $k+1$ 個狀態要計算；
> 又或是 $n$ 很小，而 $W$ 偏大的情況下，也會導致整個表格需要計算的狀態比例較低。
> 除了這兩種情況，基本上 top-down 的效率不見得會比較好（就算有也相差不到哪裡）。
<hr class="thin">
我們可以發現，每次 $dp[i]$ 都只會用到 $dp[i-1]$ 的部分，
因此我們可以把空間進行優化，這個技巧叫 rolling。
（每次將運算完的結果放入 `dp[0]`，而 `dp[1]` 留給下次運算使用）
:::spoiler
```cpp!
int O1_knapsack_problem() {
int n, W;
cin >> n >> W;
vector<int> w(n), v(n);
for (int i{0}; i < n; ++i) cin >> w[i] >> v[i];
vector<vector<int>> dp(2, vector<int>(W + 1, 0));
// 只考慮第 0 項
for (int j{w[0]}; j <= W; ++j) dp[0][j] = v[0];
for (int i{1}; i < n; ++i) {
for (int j{0}; j <= W; ++j)
if (w[i] > j) dp[1][j] = dp[0][j]; // 物品重量大於重量限制
else dp[1][j] = max(dp[0][j], v[i] + dp[0][j - w[i]]);
swap(dp[0], dp[1]);
}
return dp[0][W];
}
```
:::
<br>
空間複雜度優化至 $O(W)$。
<hr class="thin">
又可以發現， $dp[i][j]$ 只會用到 $dp[i-1][k]\;\mid\;k\le j$，只要改一下迴圈 `j` 的順序，
就可以避免覆蓋到還需要使用的值，進一步優化。
:::spoiler
```cpp!
int O1_knapsack_problem() {
int n, W;
cin >> n >> W;
vector<int> w(n), v(n);
for (int i{0}; i < n; ++i) cin >> w[i] >> v[i];
vector<int> dp(W + 1, 0);
// 只考慮第 0 項
for (int j{w[0]}; j <= W; ++j) dp[j] = v[0];
for (int i{1}; i < n; ++i) {
for (int j{W}; j >= 0; --j)
if (w[i] <= j) dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
}
return dp[W];
}
```
:::
<hr class=dotted>
### 無限背包問題（unbounded knapsack problem）
:::info
現在有 $n$ 個物品，每個物品都有無限多個，價值為 $v_i$，重量為 $w_i$；
現在有一個背包，可以容納重量不超過 $W$ 的物品，
每個物品可以拿任意次數，最多可以放入多少價值的東西？
:::
這個問題就比較簡單，因為物品數量沒有限制。
令 $dp[i]$ 為重量限制為 $i$ 下，所能達到的最大價值；
假設 $dp[i]$ 有拿一個第 $j$ 個物品的話，可以達到的最大價值為 $v[j]+dp[i-w[j]]$，
而確認過所有物品的種類 $j$，也就包括所有可能性了。
（除非這個重量限制 $i$ 放不下任何物品，$dp[i]$ 也就為 $0$）
:::success
$dp[i] = \max\limits_{0\le j\lt n}(v[j]+dp[i-w[j]])$
:::
```cpp!
int unbounded_knapsack_problem() {
int n, W;
cin >> n >> W;
vector<int> w(n), v(n);
for (int i{0}; i < n; ++i) cin >> w[i] >> v[i];
vector<int> dp(W + 1, 0);
for (int i{1}; i <= W; ++i) {
for (int j{0}; j < n; ++j)
if (w[j] <= i) dp[i] = max(dp[i], v[j] + dp[i - w[j]]);
}
return dp[W];
}
```
複雜度為 $O(nW)$。
<hr class="dotted">
或是回到 0-1 背包問題的想法，
:::success
// 0-1 背包問題的狀態轉移式
$dp[i][j] = \max(dp[i-1][j],\ v_i+dp[i-1][j-w_i])$
:::
一樣從第 $i$ 個物品的角度來看，
如果 $dp[i][j]$ 的最佳解有拿第 $i$ 個物品，
因為每種物品數量無限，子問題也還有可能繼續拿，
所以狀態還是在 $dp[i]$ 而非 $dp[i-1]$；
如果 $dp[i][j]$ 的最佳解根本沒有拿第 $i$ 個物品，
$dp[i][j]$ 跟 $dp[i-1][j]$ 的答案就會一樣；
同樣地，這樣就有考慮了所有可能性。
:::success
$dp[i][j] = \max(dp[i-1][j],\ v_i+dp[i][j-w_i])$
:::
:::spoiler
```cpp!
int unbounded_knapsack_problem() {
int n, W;
cin >> n >> W;
vector<int> w(n), v(n);
for (int i{0}; i < n; ++i) cin >> w[i] >> v[i];
vector<int> dp(W + 1, 0);
for (int i{0}; i < n; ++i) {
for (int j{w[i]}; j <= W; ++j)
dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
}
return dp[W];
}
```
:::
<br>
> 進行 rolling 的優化後，$dp[i-1][j]$ 自動就會轉換到 $dp[i][j]$，
> 因為他們放在同個位置（第二維度 $j$ 相同）。
進行空間優化後，兩個想法雖然不同，程式碼卻很相似。
> 因為這次 $dp[i][j]$ 反而是要用到 $dp[i][k]\;\mid\;k\le j$，
> 所以要先計算完 $dp[i][k]$，所以 `j` 一樣從小到大。
<hr class="dotted">
### 有限背包問題（bounded knapsack problem）:bulb:
:::info
現在有 $n$ 個物品，每個物品有 $m_i$ 個，價值為 $v_i$，重量為 $w_i$；
現在有一個背包，可以容納重量不超過 $W$ 的物品，
每個物品只能拿不超過 $m_i$ 個，最多可以放入多少價值的東西？
:::
仿照 0-1 背包問題，第 $i$ 個物品不拿，拿 $1$ 個，拿 $2$ 個...
:::success
$dp[i][j] = \max\limits_{0\le k\le m_i}(v_i\times k+dp[i-1][j-w_i\times k])$
:::
```cpp!
int bounded_knapsack_problem() {
int n, W;
cin >> n >> W;
vector<int> m(n), w(n), v(n);
for (int i{0}; i < n; ++i) cin >> m[i] >> w[i] >> v[i];
vector<vector<int>> dp(n, vector<int>(W + 1, 0));
// 只考慮第 0 項
for (int j{w[0]}; j <= W; ++j) dp[0][j] = v[0] * min(j / w[0], m[0]);
for (int i{1}; i < n; ++i)
for (int j{0}; j <= W; ++j)
for (int k{0}; k <= m[i]; ++k)
dp[i][j] = max(dp[i][j], v[i] * k + dp[i - 1][j - w[i] * k]);
return dp[n - 1][W];
}
```
複雜度為 $O(TW)$，$T$ 為 $m_i$ 總和。
<hr class="dotted">
第 $i$ 種物品有 $m_i$ 個，進行分堆，每堆分別有 $1,2,\dots,2^k$ 與 $y$ 個物品，
令 $x=1+2+\dots+2^k=2^{k+1}-1$，則 $x+y=m_i$ 且 $x\ge y$，所以 $x\ge \frac{m_i}{2}$。
現在假設最佳解要從第 $i$ 種物品的 $m_i$ 個中取出 $a$ 個，
若 $a\le \frac{m_i}{2}$，可以從 $x$ 當中取出幾堆組成 $a$ 個；
若 $a\gt \frac{m_i}{2}$，則 $m_i-a\le \frac{m_i}{2}$，可以從 $x$ 當中選幾堆不取，剩下的加總剛好為 $a$ 個。
> $x$ 中的每堆剛好對應二進制中的每個位元，
> 因此可以組成 $0\sim x$ 中的任意數。
每種物品都分堆，接著每堆當作一個物品，直接轉為 0-1 背包問題。
:::spoiler
```cpp!
int bounded_knapsack_problem() {
int _n, W;
cin >> _n >> W;
vector<int> _m(n), _w(n), _v(n);
for (int i{0}; i < n; ++i) cin >> _m[i] >> _w[i] >> _v[i];
vector<int> m{}, w{}, v{};
for (int i{0}; i < n; ++i) {
int p{1}; // 2^k
while (p < _m[i]) {
_m[i] -= p;
m.push_back(p), w.push_back(p * _w[i]), v.push_back(p * _v[i]);
p *= 2;
}
m.push_back(_m[i]), w.push_back(_m[i] * _w[i]), v.push_back(_m[i] * _v[i]);
}
int n{w.size()};
// 0-1 背包問題
...
```
:::
<br>
複雜度為 $O(TW)$，$T=\sum\limits_{i=0}^{n-1}\log(m_i)$。
<hr class="dashed">
## [最長公共子序列（LCS, longest common subsequence）](https://leetcode.com/problems/longest-common-subsequence/)
:::info
給定二個字串 $A,B$，請找出最長公共子序列。
:::
> 一個字串的子序列，是從原字串刪去一些字元後，
> 不改變其它字元順序而形成的新字串。
> 令 $s_i$ 代表字串 $S$ 的第 $i$ 個字元，
> $S_i=s_1\dots s_i$ （$S_0$ 為空字串）。
令 $dp[i][j]$ 為 $A_i, B_j$ 兩個子字串的 LCS 的長度；
先來討論 $A_i, B_j$ 兩個子字串的 LCS，從尾端字元 $a_i, b_j$ 的觀點出發；
如果 $a_i, b_j$ 相等並都在 LCS 中，必然是 LCS 的最後一個字元，
而 LCS 的長度必然等於 $A_{i-1}, B_{j-1}$ 兩個子字串的 LCS 的長度加一；
如果 $a_i$ 不在 LCS 中，那 LCS 的長度會跟 $A_{i-1}, B_{j}$ 兩個子字串的 LCS 的長度一樣；
如果 $b_j$ 不在 LCS 中，那 LCS 的長度會跟 $A_{i}, B_{j-1}$ 兩個子字串的 LCS 的長度一樣，
全部的情況就只有這三種可能了。
:::success
$dp[i][j] = \begin{cases}
\max(dp[i-1][j-1]+1,\max(dp[i-1][j], dp[i][j-1])),&\text{if}\ a_i=b_j\\
\max(dp[i-1][j], dp[i][j-1]),&\text{if}\ a_i\neq b_j
\end{cases}$
:::
> 為什麼不從 $a_i$（$b_j$）在 LCS 中去考慮呢？
> 這樣就要找到對應的 $b_k$（$a_k$），才能夠正確的切分子問題。
> 「$a_i$ 不在 LCS 中」與「$b_j$ 不在 LCS 中」是不是有可能同時發生？
> 的確，兩種情況是有交集的，但在分為子問題 $dp[i-1][j]$／$dp[i][j-1]$ 之後，
> 也沒有要求 $j$／$i$ 一定要包含在子問題的 LCS 中，所以並不衝突。
```cpp!
int LCS(const string& A, const string& B) {
vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
for (int i{1}; i <= A.size(); ++i)
for (int j{1}; j <= B.size(); ++j) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
// 因為 A, B 是 0-indexed，透過 -1 調整
if (A[i - 1] == B[j - 1])
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
return dp[A.size()][B.size()];
}
```
<hr class="thin">
目前為止我們都只有在找最佳值（optimal value），
那如果要找出一組最佳解（an optimal solution）呢？
只要透過動態規劃的表格回溯就可以了。
```cpp!
string LCS(const string& A, const string& B) {
// ...
string ans{};
int i{A.size()}, j{B.size()};
while (dp[i][j]) {
if (dp[i][j] == dp[i - 1][j]) --i;
else if (dp[i][j] == dp[i][j - 1]) --j;
else ans += A[i - 1], --i, --j;
}
return reverse(ans.begin(), ans.end()), ans;
}
```
基本上動態規劃的問題，都可以用這樣的概念找出最佳解。
<hr class="dashed">
看完這麼多動態規劃的問題，應該可以發現，
分治法通常是將問題切成幾個差不多大小的子問題，再將答案結合起來；
而動態規劃則將問題**拆解成稍為小一點的子問題**，再從中選一個最佳的，
而**動態規劃就好像暴力法**，基本上就是把每種可能都試過。
---
# 貪心法（Greedy Algorithm）
若問題可以透過貪心法求解，通常就是最好的算法了；那什麼問題又適用？
## 貪心問題的特性
第一個一樣是**最佳子結構（optimal substructure）**。
第二個則是**貪婪選擇性（greedy-choice property）**，只需要做當下最佳的選擇即可。
> We can assemble a globally optimal solution by making locally optimal(greedy) choices. In other words, when we are considering which choice to make, we make the choice that looks best in the current problem, **without considering results from subproblems.**[^CLRSgreedy]
<hr class="dashed">
:::info
有 $10$ 元、$5$ 元、$1$ 元的硬幣，如果要拿出 $x$ 元，最少可以只用幾個硬幣？
:::
一個很直觀的想法是，優先選擇面額不超過 $x$ 中最大的硬幣。
> #### 證明
> 這邊用 $x$ 大於 $10$ 的情況來討論，
> 假設有一組最佳解中，不包含任何 $10$ 元硬幣；
> 因為 $1$ 與 $5$ 都是 $10$ 的因數，
> 我們一定可以找出好幾個硬幣加在一起總額為 $10$ 元，
> 只要將它們換成一個 $10$ 元硬幣，就能減少總硬幣數，
> 與假設衝突；
> 因此得證，若 $x$ 大於 $10$ 時，任何一組最佳解一定包含有 $10$ 元硬幣。
既然知道了任意一組最佳解中一定有面額不超過 $x$ 中最大的硬幣，
那就拿一個這樣的硬幣，剩下就是子問題了。
```cpp!
int f(int x) {
if (x >= 10) return 1 + f(x - 10);
if (x >= 5) return 1 + f(x - 5);
if (x >= 1) return 1 + f(x - 1);
}
```
可以加快貪心選擇的過程，達到 $O(1)$ 的複雜度。
```cpp!
int f(int x) {
int res{0};
res += x / 10, x %= 10;
res += x / 5, x %= 5;
res += x;
return res;
}
```
> 如果面額大的硬幣不是面額小的硬幣的倍數，
> 貪心法就不適用了，需要改為動態規劃求解。
<hr class="dashed">
### 連續背包問題（fractional knapsack problem）
:::info
現在有 $n$ 個物品，每個物品只有一個，價值為 $v_i$，重量為 $w_i$；
現在有一個背包，可以容納重量不超過 $W$ 的物品，
每個物品可以只拿部分走，最多可以放入多少價值的東西？
:::
定義問題為用集合 $S$ 中的物品，在重量限制 $L$ 下，可以放入多少價值的東西。
每次儘量拿單位重量的價值最大的物品，子問題則變為，
用剩下的物品，在剩下的重量限制下，可以放入多少價值的東西。
:::spoiler 證明
> 集合 $S$ 中單位重量的價值最大者 $m$，
> 一定有 $\min(w_m, L)$ 單位重量在某一組最佳解之中。
>
> 反證法：
> 假設沒有任何一組最佳解包含 $\min(w_m, L)$ 單位重量的 $m$，
> 那任意一組最佳解就能只包含了 $x\mid x\lt \min(w_m, L)$ 單位重量的 $m$；
> 可是只要將這組最佳解中 $\min(w_m, L)-x$ 單位重量的其它物品換為 $m$，
> 就可以達到不小於它的價值，與假設衝突，
> 所以一定有一組最佳解包含 $\min(w_m, L)$ 單位重量的 $m$。
> （這裡考慮到物品單位重量的價值可能相同，證明就比較繁瑣）
:::
<br>
這邊證明了至少有一組最佳解中，包含單位重量的價值最大的物品，
所以就不需要考慮其他可能性，照著這個貪心的策略，
再繼續求解剩餘的子問題即可。
> 這邊就是貪心法與動態規劃最不一樣的地方，在父問題時，
> 就可以確認有某種選擇一定是最好的，可以達到最佳值（最佳解可能不唯一），
> 並不需要再考慮其他可能性。
```cpp!
int fractional_knapsack_problem() {
int n, W;
cin >> n >> W;
vector<pair<int, int>> vt(n);
for (auto& [w, v] : vt) cin >> w >> v;
sort(vt.begin(), vt.end(),
[](const pair<int, int>& a, const pair<int, int>& b) {
return a.first * b.second > b.first * a.second;
}
);
double ans{0};
for (int i{0}; i < n; ++i)
if (W >= vt[i].second) {
ans += vt[i].first;
W -= vt[i].second;
// 子問題的物品集合變為 vt[i+1:n)（其他物品都拿光了）
} else {
// 只拿部分走
ans += double(vt[i].first * W) / vt[i].second;
break;
}
}
```
<hr class="dashed">
**比賽中通常不需要也不會去這麼嚴謹的證明算法的正確性**，
但還是會有一定的理由或論述來支撐，除非不在意 <font color="#e74c3c">WA</font><sup class="footnote-ref"><a href="#fn1" id="fnref1:1" smoothhashscroll=""></a></sup>。
> 別忘了，除了 Greedy algorithm 以外，有些問題解法的想法很貪心，
> 在競程中（或口語上）也會稱之是 Greedy 的算法。
---
# References
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein (2009). "Introduction to Algorithms (Third Edition)".
* 演算法筆記 - [Knapsack Problem](http://web.ntnu.edu.tw/~algo/KnapsackProblem.html)
* [MIT 6.006 Introduction to Algorithms, 19. Dynamic Programming I](https://youtu.be/OQ5jsbhAv_M)
---
# 練習題
| Problem | Tags |
|:-:|:- |
| **Basic** |
| [彩彩劈瓦 ](https://oj.leo900807.tw/problems/8) | DP |
| [Let Me Count The Ways](https://zerojudge.tw/ShowProblem?problemid=d133) | DP |
| [K Balanced Teams](https://codeforces.com/contest/1133/problem/E) | DP |
| [No Nine](https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050ff4/0000000000051183) | DP |
| [CD](https://onlinejudge.org/external/6/624.pdf) | 01背包 |
| [Lowest Price in Town](https://onlinejudge.org/external/109/10980.pdf) | 無限背包 |
| [Vacation](https://onlinejudge.org/external/101/10192.pdf) | LCS |
| [貪婪之糊](https://zerojudge.tw/ShowProblem?problemid=d652) | Greedy |
| [錢包的路](https://tioj.ck.tp.edu.tw/problems/1636) | Greedy |
| [Minimum Triangulation](https://codeforces.com/problemset/problem/1140/D) | Greedy|
| **Challenging** |
| [UVa 10635 - Prince and Princess](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1576) | |
[^optss]: Wikipedia - [Optimal substructure](https://en.wikipedia.org/wiki/Optimal_substructure)
[^olsp]: Wikipedia - [Overlapping subproblems](https://en.wikipedia.org/wiki/Overlapping_subproblems)
[^CLRSgreedy]: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein (2009). "Introduction to Algorithms (Third Edition)", p.424.
<style>
hr.thin {
height: 0.5px;
}
hr.dotted {
border-top: dotted;
height: .0em;
color: #777777;
background-color: #ffffff;
}
hr.dashed {
border-top: dashed;
height: .0em;
color: #777777;
background-color: #ffffff;
}
/* Gradient transparent - color - transparent */
hr.gradient {
border: 0;
height: 1px;
background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0));
}
/* Flaired edges, by Tomas Theunissen */
hr.flaired {
overflow: visible;
height: 30px;
border-style: solid;
border-color: black;
border-width: 1px 0 0 0;
border-radius: 20px;
background-color: #ffffff;
}
hr.flaired:before { /* Not really supposed to work, but does */
display: block;
content: "";
height: 30px;
margin-top: -31px;
border-style: solid;
border-color: black;
border-width: 0 0 1px 0;
border-radius: 20px;
}
</style>
Sign in with Wallet
Connect another wallet