# 110 選手班 - 動態規劃 ###### tags: `宜中資訊` `CP` Ccucumber12 2021.08.17 --- ## Outline - Knapsack - 滾動陣列 - 狀態壓縮 - Sum-over-Subset - Optimization --- ## Knapsack ---- ### 0-1 Knapsack - 1 - 給定 $N$ 個物品，第 $i$ 個物品重量$w_i$，價值$v_i$ - 背包容量 $W$ - 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？ - $N \leq 100$，$W \leq 10^5$ ---- 每個物品 - 0: 不選，重量$+0$，價值$+0$ - 1: 選擇，容量$-w_i$，價值$+v_i$ ---- - $\text{dp}[i][j]:=$只能選前 $i$ 個物品的情況下，背包容量為 $j$ 的最大價值總和。 - 考慮第 $i$ 個物品 - 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$ - 1: $\text{dp}[i][j] = \text{dp}[i-1][j-w_i]+v_i$ - Ans: $\text{dp}[N][W]$ ---- Complexity - Time: $\mathcal{O}(NW)$ - Space: $\mathcal{O}(NW)$ ---- ### 0-1 Knapsack - 2 - 給定 $N$ 個物品，第 $i$ 個物品重量$w_i$，價值$v_i$ - 背包容量 $W$ - 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？ - $N \leq 100，W \leq 10^9，\sum v_i \leq 10^5$ ---- - $\text{dp}[i][j]:=$只能選前 $i$ 個物品的情況下，價值總合為 $j$ 的最小重量總和。 - 考慮第 $i$ 個物品 - 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$ - 1: $\text{dp}[i][j] = \text{dp}[i-1][j-v_i]+w_i$ ---- Answer - For every $\text{dp}[i][j] \leq W$ - Max $j$ ---- Initialize - $\text{dp}[i][0] = 0$ - $\text{dp}[i][j] = \inf, (j > 0)$ ---- Complexity - Time: $\mathcal{O}(N\sum v_i)$ - Space: $\mathcal{O}(N\sum v_i)$ ---- ### 0-1 Knapsack - 4 - 給定 $N$ 個物品，第 $i$ 個物品重量$w_i$，價值$v_i$ - 背包容量 $W$ - 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？ - $N \leq 20，W \leq 10^9$ ---- Enumeration - $\mathcal{O}(2^N)$ ---- ### 0-1 Knapsack - 5 - 給定 $N$ 個物品，第 $i$ 個物品重量$w_i$，價值$v_i$ - 背包容量 $W$ - 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？ - $N \leq 40，W \leq 10^9$ ---- Enumeration - $\mathcal{O}(2^N)$ ? ---- 折半枚舉 - set $A$：item $[1,\ 20]$ - set $B$：item $[21,\ 40]$ - combine $A$ and $B$ ---- Combine - subset of $A$：$a\ (w_a,\ v_a)$ - for all subset of $B$：$b$ - $w_b \leq W - w_a$ - Find max $v_b$ - Sort + Two pointers ---- Time Complexity - enumerate $A$: $\mathcal{O}(2^\frac{N}{2})$ - enumerate $B$: $\mathcal{O}(2^\frac{N}{2})$ - Combine: - Sort: $\mathcal{O}(2^\frac{N}{2}\log 2^\frac{N}{2})=O(N \times 2^\frac{N}{2})$ - Two pointers: $\mathcal{O}(2^\frac{N}{2})$ - Total: $\mathcal{O}(N \times 2^\frac{N}{2})$ ---- ### Unbounded Knapsack - 給定 $N$ 種物品，第 $i$ 種物品重量$w_i$，價值$v_i$ - 背包容量 $W$ - 選擇任意數量物品，每種不限個數，使得重量總和不超過容量，請問最大價值總和為何？ - $N \leq 100，W \leq 10^5$ ---- - $\text{dp}[i][j]:=$只能選前 $i$ 個物品的情況下，背包容量為 $j$ 的最大價值總和。 - 考慮第 $i$ 個物品 - 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$ - 1: $\text{dp}[i][j] = \text{dp}[i-1][j-w_i]+v_i$ - 2: $\text{dp}[i][j] = \text{dp}[i-1][j-2w_i]+2v_i$ - 3: $\text{dp}[i][j] = \text{dp}[i-1][j-3w_i]+3v_i$ - $\dots$ ---- - $\text{dp}[i][j] = \text{dp}[i-1][j - w_i] + v_i$ - 每項物品只能選一次 - 01背包 - $\text{dp}[i][j] = \text{dp}[i][j - w_i] + v_i$ - 每項物品選完之後還能選 - 無限背包 ---- - $\text{dp}[i][j]:=$只能選前 $i$ 個物品的情況下，背包容量為 $j$ 的最大價值總和。 - 考慮第 $i$ 個物品 - 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$ - 1: $\text{dp}[i][j] = \text{dp}[i][j-w_i]+v_i$ ---- Complexity - Time: $\mathcal{O}(NW)$ - Space: $\mathcal{O}(NW)$ ---- ### Bounded Knapsack - 給定 $N$ 種物品，第 $i$ 種物品重量$w_i$，價值$v_i$，共有$k_i$個 - 背包容量 $W$ - 選擇任意數量物品，使得重量總和不超過容量，請問最大價值總和為何？ - $N \leq 100，W \leq 10^5$ ---- - $\text{dp}[i][j]:=$只能選前 $i$ 個物品的情況下，背包容量為 $j$ 的最大價值總和。 - 考慮第 $i$ 個物品 - 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$ - 1: $\text{dp}[i][j] = \text{dp}[i-1][j-w_i]+v_i$ - 2: $\text{dp}[i][j] = \text{dp}[i-1][j-2w_i]+2v_i$ - $\dots$ - $k_i$: $\text{dp}[i][j] = \text{dp}[i-1][j-k_iw_i]+k_iv_i$ ---- #### 砝碼問題 想要製造出 $1 \sim 100$ 之間任意整數的重量，請問最少需要多少個砝碼？ ---- - 二進位 - $1, 2, 4, 8, 16, 32, 37$ - Ans: $\lceil \log_2 100 \rceil$ ---- - 想要製造出 $1 \sim k$ 之間任意整數的數量 - 二進位拆解成 $\log k$ 個 - 每個獨立選擇取或不取 - 0-1 背包問題 ---- Complexity Time: $\mathcal{O}(N\log kW)$ Space: $\mathcal{O}(N\log kW)$ ---- ### 混和背包 - 最多取一次 - 最多取 $k$ 次 - 可以取無限次 ---- - 0-1: 最多取一次的有限背包 - 無限: 最多取 $\frac{W}{w_i}$ 次的有限背包 ---- Solution 還是有限背包 ---- ### 二維背包 - 給定 $N$ 個物品，第$i$個物品價值$v_i$，但要消耗兩種代價$a_i$和$b_i$ - 背包兩種代價容量 $W$ 和 $U$ - 選擇一些物品，使得兩種代價總和皆不超過背包容量，請問最大價值總和為何？ - $N \leq 100$，$W,U \leq 10^3$ ---- 每個物品 - 0: 不選，容量$-0 / -0$，價值$+0$ - 1: 選擇，容量$-a_i / -b_i$，價值$+v_i$ ---- - $\text{dp}[i][j][k]:=$只能選前 $i$ 個物品的情況下，背包容量為 $j$ 和 $k$ 的最大價值總和。 - 考慮第 $i$ 個物品 - 0: $\text{dp}[i][j][k] = \text{dp}[i-1][j][k]$ - 1: $\text{dp}[i][j][k] = \text{dp}[i-1][j-a_i][k-b_i]+v_i$ - Ans: $\text{dp}[N][W][U]$ ---- Complexity Time: $\mathcal{O}(NWU)$ Space: $\mathcal{O}(NWU)$ ---- ### 限量背包 - 給定 $N$ 個物品，第 $i$ 個物品重量$w_i$，價值$v_i$ - 背包容量 $W$ - 選擇至多 $M$ 個物品，使得重量總和不超過容量，請問最大價值總和為何？ - $N,M \leq 100$，$W \leq 10^5$ ---- 每個物品 - 0: 不選，容量$-0$，個數$-0$，價值$+0$ - 1: 選擇，容量$-w_i$，個數$-1$，價值$+v_i$ ---- 二維背包 - 第一個代價 - 物品：$w_i$ - 容量：$W$ - 第二個代價 - 物品：$1$ - 容量：$M$ ---- Complexity - Time: $\mathcal{O}(NMW)$ - Space: $\mathcal{O}(NMW)$ ---- ### 分組背包 - 給定 $N$ 個物品，第 $i$ 個物品重量$w_i$，價值$v_i$，屬於組別 $k_i$ - 背包容量 $W$，物品共分為 $K$ 組 - 每組最多選擇一件物品，使得重量總和不超過容量，請問最大價值總和為何？ - $N,K \leq 100$，$W \leq 10^5$ ---- - $\text{dp}[i][j]:=$只能選前 $i$ **組**物品的情況下，背包容量為 $j$ 的最大價值總和。 - 考慮第 $i$ **組**物品 - 考慮第 $i$ 組物品內，第 $u$ 個物品 - 0: $\text{dp}[i][j] = \text{dp}[i-1][j]$ - 1: $\text{dp}[i][j] = \text{dp}[i-1][j-w_u]+v_u$ - Ans: $\text{dp}[K][W]$ ---- Complexity Time: $\mathcal{O}(NW)$ Space: $\mathcal{O}(NW)$ --- ## 滾動陣列 ---- ### 0-1 Knapsack - Space Complexity: $\mathcal{O}(NW)$ - MLE :sad: - 減少不必要的地方 ---- - $\text{dp}[i][j] = \max(\text{dp}[i-1][j], \text{dp}[i-1][j-w_i] + v_i)$ - $\text{dp}[j] = \max(\text{dp}[j], \text{dp}[j-w_i] + v_i)$ - $j$: $W \rightarrow 1$ - Space: $\mathcal{O}(W)$ ---- ### Unbounded Knapsack - $\text{dp}[i][j] = \max(\text{dp}[i-1][j], \text{dp}[i][j-w_i] + v_i)$ - $\text{dp}[j] = \max(\text{dp}[j], \text{dp}[j - w_i] + v_i)$ - $j$: $1 \rightarrow W$ - Space: $\mathcal{O}(W)$ ---- ### 路徑規劃問題 - 1 - 給定一張 $N$ 點 $M$ 邊的帶權有向圖 - 請問從 $S$ 走到 $T$，洽經過 $K$ 條邊的最短路長度 - $N,M,K \leq 3000$，Memory: 1MB ---- - $\text{dp}[i][v]:=$從 $S$ 出發洽經過 $i$ 條邊到達 $v$ 的最短路長度 - $\text{dp}[i][v] = \displaystyle\min_{(u,v) \in G}(\text{dp}[i-1][u] + W_{uv})$ - Space Complexity: $\mathcal{O}(KN)$ - Time Complexity: $\mathcal{O}(KN)$ ---- - $\text{dp}[0/1][v] = \displaystyle\min_{(u,v) \in G}(\text{dp}[1/0][u] + W_{uv})$ - $\text{dp}[i\& 1][v] = \displaystyle\min_{(u,v) \in G}(\text{dp}[i\&1 \verb=^= 1][u] + W_{uv})$ - Space Complexity: $\mathcal{O}(N)$ ---- ### 路徑規劃問題 - 2 - 給定一張 $N$ 點 $M$ 邊的帶權有向圖 - 請問從 $S$ 走到 $T$，洽經過 $K$ 條邊的最短路長度 - 請輸出解 - $N,M,K \leq 3000$，Memory: 1MB ---- 滾動陣列 - Space Complexity: $\mathcal{O}(N)$ - 無法留存過程中的點 ---- 求第 $M$ 個點 - 多開一個陣列紀錄：第 $M$ 列與之後轉移點的關係 - Space Complexity: $\mathcal{O}(N)$ ---- 考慮分治 - 每次尋找中間的點為何 - 遞迴上下部分再次尋找中間點 ---- - solve(L, R, dpL, dpR) = dpM - L: 第 L 列，遞迴左界 - R: 第 R 列，遞迴右界 - dpL: 第 L 列的起始點 - dpR: 第 R 列的終止點 - dpM: 中間點的解 - 往下遞迴 - solve(L, M, dpL, dpM) - solve(M, R, dpM, dpR) ---- - $T(K) = O(NK) + 2T(\frac{K}{2})$ - $T(K) = O(NK\log K)$ ---- Complexity - Time: $\mathcal{O}(NK\log K)$ - Space: $\mathcal{O}(N)$ - 以時間換取空間 --- ## 狀態壓縮 ---- ### TIOJ 1014 - 有 $N$ 個地鼠，分別在數線上 $1$ 到 $N$ 的整數點上 - 地鼠 $i$ 每 $t_i$ 秒會出現一次 - 玩家從 $0$ 出發，每秒可以移動一格，打地鼠時間忽略不計，請問打完所有地鼠所需的最少秒數 - $N \leq 16$ ---- - $N \leq 4$ - $\text{dp}[n][s_1][s_2][s_3][s_4] = S$ - $n$: 目前在地鼠 $n$ 的位置 - $s_i$: 是否打過地鼠 $i$ (0/1) - $S$: 最少秒數 - $\text{dp}[2][0][1][1][1] = \min\dots$ - $\text{dp}[3][0][0][1][1] + f(t, 2)$ - $\text{dp}[4][0][0][1][1] + f(t, 2)$ - Ans: $\text{dp}[i][1][1][1][1]$ ---- - $N \leq 16$ - $\text{dp}[n][s] = S$ - $s$: 二進位表示各個地鼠的狀況 - $\text{dp}[n][s] = \min(dp[i][s - (1<<i)] + f(t, n))$ - for all $i$ S.T. $(s \& (1<<i)) != 0$ - Ans: $\text{dp}[i][2^n-1]$ ---- Complexity - Time: $\mathcal{O}(N^2 \times 2^N)$ - Space: $\mathcal{O}(N \times 2^N)$ ---- ### Other - Travelling Salesman Problem - Hamilton Circuit ---- ### 3 status - $\text{dp}[s_1][s_2][s_3]...[s_n]$ - $s_i$: 三種狀態 (0 / 1 / 2) - $\text{dp}[s]$ - $s$: 轉成三進位判斷第 $i$ 個的狀態 - Complexity: $\mathcal{O}(3^N)$ --- ## Sum-over-Subset ---- - Sum-over-Subset DP - SoS DP - Möbius Transform - 莫比烏斯轉換 ---- ### Problem - $N$ 個元素形成各種子集 $S$ - 計算所有 $f(S) = \sum\limits_{S' \subseteq S}f(S')$ - 任意子集之值來自其子集之值 - 子集的子集 ---- ### Solution - 1 ```c= int subsetEnum(int S) { int subset = S, ret = 0 ; while(subset > 0) { ret += f[subset] ; subset = (subset - 1) & S ; } return ret ; } ``` ---- - 從 $\text{subset} = S$ 開始，由大到小枚舉所有子集 - 若 $\text{subset}$ 為奇數：$\text{subset}$ - 1 - 若 $\text{subset}$ 為偶數：最低位 1 變成 0，剩下的與原 $S$ 取一樣 ---- Time Complexity - 每個元素三種狀況： - 0: 不在 $S$ 裡面 - 1: 在 $S$ 裡面，但是不在 $\text{subset}$ 裡面 - 2: 在 $S$ 裡面，也在 $\text{subset}$ 裡面 - $\mathcal{O}(3^N)$ ---- ### Solution - 2 - 將 $S$ 的子集依照 **二進位下與$S$的共同後綴長度** 分類 - $N = 3$，$S = 6 = 110_{(2)}$ - $L(S,3) = \{110_{(2)}\}$ - $L(S,2) = \{110_{(2)}, 010_{(2)}\}$ - $L(S,1) = \{110_{(2)}, 010_{(2)}, 100_{(2)}, 000_{(2)}\}$ - $L(S,0) = \{110_{(2)}, 010_{(2)}, 100_{(2)}, 000_{(2)}\}$ ---- \begin{equation} \left. L(S,i) \right. = \left. \begin{cases} {S}, & \text{if}\ i = N\\ L(S,i+1), & \text{if}\ i \notin S\\ L(S,i+1) \cup L(S / {i}, i+1), & \text{otherwise} \end{cases} \right. \end{equation} ---- - 邊界條件：$L(S,N) = S$ - $S$ 第 $i$ 個 bit 為 $0$：直接取下一個bit - $S$ 第 $i$ 個 bit 為 $1$：有含$i$ + 不含$i$ ---- ```c= int dp[1 << N][N], S[N] ; void SoSDP(int n) { for(int i = 0; i < (1<<n); ++i) dp[i][n] = S[i] ; for(int i = n - 1; i >= 0; --i) { for(int s = 0; s < (1 << n); ++s) { dp[s][i] = dp[s][i + 1] ; if(s & (1<<i)) dp[s][i] += dp[s^(1<<i)][i + 1] ; } } } ``` ---- 滾動陣列 ```c= int dp[1 << N], S[N] ; void SoSDP(int n) { for(int i = 0; i < (1<<n); ++i) dp[i][n] = S[i] ; for(int i = n - 1; i >= 0; --i) { for(int s = (1<<n)-1; s >= 0; --s) { if(s & (1<<i)) dp[s] += dp[s^(1<<i)] ; } } } ``` ---- Complexity - Time: $\mathcal{O}(N2^N)$ - Space: $\mathcal{O}(2^N)$ --- ## Optimization ---- ### 單調隊列優化 - 轉移點具有單調性 - 減少轉移點的尋找過程 - 均攤分析 ---- ### CF 372C - $M$ 個煙火在數線上綻放，第 $i$ 個煙火在 $t_i$ 時，於 $a_i$ 綻放 - 若你在 $x$ 觀賞煙火 $i$，你會獲得 $b_i - |a_i - x|$ 的開心度 - 你每秒可以移動 $d$ 單位距離，並可以任意選初始位置 - 請問看完 $M$ 個煙火的最大開心度為何？ - $M \leq 300，1 \leq a_i \leq N，N \leq 1.5\times 10^5$ ---- Order - 依照時間順序觀賞煙火 - 將煙火依照 $t_i$ 排序 ---- - $\text{dp}[i][j]:=$看完第 $i$ 個煙火，且位於 $j$ 的開心度 - $\text{dp}[i][j] = \displaystyle\max_{|k-j| \leq d \times (t_i - t_{i-1})}(\text{dp}[i-1][k] + b_i - |a_i - j| )$ - Time: $\mathcal{O}(MN^2)$ ---- - $\text{dp}[i][j] = \displaystyle\max_{|k-j| \leq d \times (t_i - t_{i-1})}(\text{dp}[i-1][k]) + b_i - |a_i - j|$ - let $D = d \times (t_i - t_{i-1})$ - $\text{dp}[i][j] = \displaystyle\max_{j-D \leq k \leq j+D}(\text{dp}[i-1][k]) + b_i - |a_i - j|$ - Sliding Window - Time: $\mathcal{O}(MN)$ ---- ### 分治優化 - 轉移點具有單調性 - 縮有轉移點可能範圍 - 分治想法 ---- ### CF 321E - $N$ 個人排隊搭船，有 $K$ 艘船依次前來載人 - 第 $i$ 艘船來時，前面 $q_i$ 個人就會上船 - 給定第 $i$ 人與第 $j$ 人的陌生度 $u[i][j]$，只要兩人在同一艘船上，就會加上此陌生度 - 請分配 $q_i$ 使得陌生度總和最小 - $N \leq 4000，K \leq 800，1\leq u[i][j] \leq 9$ ---- - $\text{dp}[i][j]:=$前 $j$ 個人已經用 $i$ 艘船載走的陌生度 - $\text{dp}[i][j] = \displaystyle\min_{k < j}(\text{dp}[i-1][k] + C(k, j))$ - $C(k,j):=$第 $k$ 到第 $j$ 個人在同一艘船上的陌生度總和 - Time: $\mathcal{O}(KN^2)$ ---- - $C(k,j)$ 隨長度成長極快 - 盡量越平均越好 - 當 $j$ 增加時， $k$ 理當也要隨其增加 - ( 直覺 ) ---- - 若 $\text{dp}[i][k]$ 的轉移點為 $x$ - $\text{dp}[i][k+1]$ 的轉移點 $\geq x$ - $\text{dp}[i][k-1]$ 的轉移點 $\leq x$ ---- - 計算 $\text{dp}[i][1 \sim N]$ - 先計算 $\text{dp}[i][mid]$ 轉移點為 $x$ - 分治遞迴 - $\text{dp}[i][1 \sim mid]$ 轉移點 $[1 \sim x]$ - $\text{dp}[i][mid \sim N]$ 轉移點 $[x \sim N]$ - Time: $\mathcal{O}(KN\log N)$ ---- ### 斜率優化 - 轉移式為線性函數 - 所有轉移可能為一個 下/上 凸包 ---- - $\text{dp}[i] = \displaystyle\max_{j \leq R_i}(a_jx_i + b_j) + c_i$ - $R_i$ 是遞增序列 - $a_jx_i + b_j$ 為線性函數 ---- - $R_i$ 增加 $\rightarrow$ 插入新的直線 - 尋找最大值 $\rightarrow$ 找點 $x$ 的最大值 - 凸包二分搜 ----  ---- - $\text{dp}[i] = \max\{(a_i - a_j)^2 + c_j\}$ - $\text{dp}[i] = \max\{a_i^2 - 2a_ia_j + a_j^2 + c_j\}$ - $\text{dp}[i] = \max\{(-2a_j)a_i + (a_j^2+c_j)\} + a_i^2$ - 斜率優化 --- ## Credit - OI wiki - IONC - IOIC - http://www2.lssh.tp.edu.tw/~hlf/class-1/lang-c/DP.pdf - https://codeforces.com/blog/entry/63823 ---- ### AtCoder DP X-Tower - There are $N$ blocks, block $i$ has a weight of $w_i$, a solidness of $s_i$ and a value of $v_i$ - Choose some blocks to build a tower which follows the condition: - For each block $i$, the sum of weights of blocks above it is not greater than $s_i$ - Find the maximum possible sum of value in the tower - $N \leq 10^3，w_i,s_i \leq 10^4$