--- 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>