部落格園同步
前置知識：
- 淺談單調隊列
- 簡單背包問題
這篇文章我們主要研究 單調隊列優化 dp \text{dp} dp 如何用于背包問題 和 部分特殊背包問題的優化方式。
01 \text{01} 01 背包問題
n n n 個物品，背包體積為 V V V，每個物品有 v i v_i vi（價值）和 w i w_i wi（重量），每個物品隻有 1 1 1 個。求在不超過背包體積的情況下能獲得的最大價值。
n , V , v i , w i ≤ 1 × 1 0 3 n,V,v_i,w_i \leq 1 \times 10^3 n,V,vi,wi≤1×103，時間限制 1 s 1s 1s，空間限制 16 M B 16MB 16MB.
簡單的考慮，用 f i , j f_{i,j} fi,j 表示前 i i i 個物品，背包體積為 j j j 的答案，則易得：
f i , j = max ( f i − 1 , j , f i − 1 , j − w i + v i ) f_{i,j} = \max(f_{i-1,j} , f_{i-1 , j-w_i} + v_i) fi,j=max(fi−1,j,fi−1,j−wi+vi)
這樣可以在 O ( n V ) \mathcal{O}(nV) O(nV) 的時間内解決問題。
但是你發現空間隻有 16 MB 16 \text{MB} 16MB，由于 i i i 的決策隻取決于上一行同一列，是以可以直接降維，得：
f j = max ( f j , f j − w i + v i ) f_j = \max(f_j , f_{j-w_i} + v_i) fj=max(fj,fj−wi+vi)
注意 j ≥ w i j \geq w_i j≥wi 的隐約限制。
僞代碼如下：
for (i=1;i<=n;i++)
for (j=V;j>=w[i];j--)
f[j] = max(f[j] , f[j-w[i]] + v[i]);
O ( n V ) \mathcal{O}(nV) O(nV) 是最優的算法。今天我們所要實作的，僅僅是，把所有的背包算法複雜度都降為 O ( n V ) \mathcal{O}(nV) O(nV).
倒叙枚舉 - 小細節
你可能會在代碼裡注意到一行：
為什麼是倒序枚舉呢？它和
等價嗎？
這是一個初學者常常犯的錯誤，這兩種寫法并不等價。可以運用這種寫法去解決完全背包。
如果你是正序枚舉的話，你會發現， i i i 号物品會被重複使用很多次。比方說 w i = 2 , v i = 3 w_i = 2 , v_i = 3 wi=2,vi=3 時，那麼 j = 4 j=4 j=4 就會從 j = 2 j=2 j=2 轉移過來，此時 程式已經把 i i i 物品用了 2 2 2 次，這樣是不可取的。而反之在完全背包中則是可取的，因為完全背包問題是 無限個數 ，可以這樣寫。
當然如果你倒序枚舉的話，此時對于所有 j = w i , j = 2 × w i ⋯ ⋯ j = w_i , j = 2 \times w_i \cdots \cdots j=wi,j=2×wi⋯⋯ 中，就隻會更新 j = w i j=w_i j=wi 的，因為倒序的時候 j j j 從 j − w i j-w_i j−wi 來，前一個還沒有推出來就推導後一個，肯定沒有答案——這樣正好是我們所求的。而 j = w i j=w_i j=wi 有答案的原因就是因為本身的一次更新。
之後遇到的各種 dp \text{dp} dp 都會出現類似此類的問題，大家一定要小心！
完全背包問題
n n n 個物品，背包體積為 V V V，每個物品有 v i v_i vi（價值）和 w i w_i wi（重量），每個物品有無限個。求在不超過背包體積的情況下能獲得的最大價值。
n , V , v i , w i ≤ 1 × 1 0 3 n,V,v_i,w_i \leq 1 \times 10^3 n,V,vi,wi≤1×103，時間限制 1 s 1s 1s，空間限制 16 M B 16MB 16MB.
這樣你會發現一個問題，你不知道有多少個！
當然你可以用 ⌊ V v i ⌋ \lfloor \frac{V}{v_i} \rfloor ⌊viV⌋ 來表示數量，考慮枚舉。
同樣的 f i , j f_{i,j} fi,j，我們可以知道：
f i , j = max k = 0 ⌊ V v i ⌋ ( f i − 1 , j − k × w i + k × v i ) f_{i,j} = \max_{k=0}^{\lfloor \frac{V}{v_i} \rfloor}(f_{i-1,j-k \times w_i} + k \times v_i) fi,j=k=0max⌊viV⌋(fi−1,j−k×wi+k×vi)
大前提是 j ≥ k × w i j \geq k \times w_i j≥k×wi，這樣轉移的複雜度是 O ( n V w i ) \mathcal{O}(nVw_i) O(nVwi)，降維之後應該可以通過。
考慮一個簡單的加強：
n , V , v i , w i ≤ 1 × 1 0 4 n,V,v_i,w_i \leq 1 \times 10^4 n,V,vi,wi≤1×104，空間限制 128 M B 128MB 128MB.
我們将在下面的研究中，解決這個問題。
多重背包問題
n n n 個物品，背包體積為 V V V，每個物品有 v i v_i vi（價值）和 w i w_i wi（重量），每個物品有 num i \text{num}_i numi 個。求在不超過背包體積的情況下能獲得的最大價值。
n , V , v i , w i ≤ 1 × 1 0 4 n,V,v_i,w_i \leq 1 \times 10^4 n,V,vi,wi≤1×104，時間限制 1 s 1s 1s，空間限制 128 M B 128MB 128MB.
顯然我們按照完全背包的方法就可以了，但是 O ( n V w i ) \mathcal{O}(nVw_i) O(nVwi) 是不可能通過 1 0 4 10^4 104 的！是以我們需要考慮，如何優化這個問題。
實際上不用單調隊列也可以優化，我們先來講著名的背包優化的幾個方法。
二進制拆分
二進制！這是個熟悉的東西。
實際上我們背包的瓶頸在于兩個：背包物品過多，背包容積過大，背包物品數量過多。
容積過大可能會想到離散，但是這不是排序之類隻用知道大小的問題啊！容積是不能突破的，考慮優化物品個數。物品個數怎麼可能優化呢？數量？
那你可能會說，這和二進制又有什麼關系？
下面我們來說一說吧。
用二進制表示數
用集合 s s s 表示二的幂次集，則 s = { 2 0 , 2 1 ⋯ 2 ∞ } s = \{ 2^0 , 2^1 \cdots 2^{\infty}\} s={20,21⋯2∞}.每個正整數都可以用若幹個 s s s 集合内的元素相加而成。就是說每個數一定能被分解成若幹二的幂次的數之和。
10 = 2 + 8 10 = 2 +8 10=2+8
100 = 64 + 32 + 4 100 = 64 + 32 +4 100=64+32+4
1000 = 512 + 256 + 128 + 64 + 32 + 8 1000 = 512 + 256 + 128 + 64 + 32 + 8 1000=512+256+128+64+32+8
如何證明？
顯而易見，每個數都能被二進制表示。比方說 1 0 10 = 100 1 2 10_{10} = 1001_2 1010=10012.
那麼，用計數原則， 100 1 2 = 1 × 2 0 + 0 × 2 1 + 0 × 2 2 + 1 × 2 3 1001_2 = 1 \times 2^0 + 0 \times 2^1 + 0 \times 2^2 + 1 \times 2^3 10012=1×20+0×21+0×22+1×23
這樣就證明結束了，你沒有發現嗎？
拆分原理
将一個 { v i , w i , n u m i } \{ v_i , w_i , num_i\} {vi,wi,numi} 的物品，通過 n u m i num_i numi 進行拆分。
本來假設一個物品有 7 7 7 個，你可以把它拆開成 1 , 2 , 4 1,2,4 1,2,4 個，對這三個物品進行 01 01 01 背包，你就可以得到 1 − 7 1 - 7 1−7 所有可能的答案。最後你把不取的答案單獨做一遍就可以了。
原理就是， n n n 最多被拆成 log n \log n logn 個二的幂次的數之和，這樣保證了時間複雜度是 O ( n V log w i ) \mathcal{O}(nV \log w_i) O(nVlogwi) 的。
僞代碼
for(i=1;i<=n;i++) {
read(x) , read(y) , read(z);
for(j=1;j<=z;j<<=1) v[++cnt]=x*j,w[cnt]=y*j,z-=j;
if(z) v[++cnt]=x*z,w[cnt]=y*z;
}
// use array v and w to do 01 backpack
單調隊列
顯然， 1 0 4 10^4 104 的資料可以把二進制拆分卡死。我們需要嚴格去掉 log \log log.
再看一眼這個狀态轉移：
f i , j = max k = 0 num i ( f i − 1 , j − k × w i + k × v i ) f_{i,j} = \max_{k=0}^{\text{num}_i}(f_{i-1,j-k \times w_i} + k \times v_i) fi,j=k=0maxnumi(fi−1,j−k×wi+k×vi)
你會發現，這不是一段連續的決策！這是斷續的。
但是，你會發現這樣一個問題。
f i − 1 , j , f i − 1 , j − w i , f i − 1 , j − 2 × w i ⋯ f i − 1 , j − num i × w i f_{i-1 , j} , f_{i-1 , j - w_i} , f_{i-1 , j - 2 \times w_i} \cdots f_{i-1 , j - \text{num}_i \times w_i} fi−1,j,fi−1,j−wi,fi−1,j−2×wi⋯fi−1,j−numi×wi，這是所有 f i , j f_{i,j} fi,j 的決策點。
你會發現，這些決策點是同行等差列的，每兩個決策點隔着一個 w i w_i wi. 這非常好！
餘數構造連續決策
你會發現，你可以把 V V V 按照模 w i w_i wi 進行分類，餘數相同的肯定是一類的。
那樣我們就可以把這一段當成連續的決策去做，因為實際上枚舉餘數 mo \text{mo} mo 和目前周期編号 k k k. 因為 k k k 是連續的，那麼 mo + k × w i \text{mo} + k \times w_i mo+k×wi 實際上就是目前的決策點。這樣我們構造出了若幹段連續的決策。
時間複雜度分析
對 n n n 個物品每次做一次，是以 O ( n ) \mathcal{O}(n) O(n).
然後同時枚舉餘數和 k k k，因為 mo × k ≤ V \text{mo} \times k \leq V mo×k≤V，是以本質上這兩重循環的 ∑ \sum ∑ 不會超過 V V V，是 O ( V ) \mathcal{O}(V) O(V).
按照單調隊列每個節點進出一次的原理， O ( n V ) \mathcal{O}(nV) O(nV) 的目标已然達成。
for(i=1;i<=n;i++) {
read(v) , read(w) , read(num);
num=min(num,V/v);
for(mo=0;mo<v;mo++) {
l=r=0;
for(k=0;k<=(V-mo)/v;k++) {
x=k,y=f[k*v+mo]-k*w;
while(l<r && q[l].pos<k-num) l++;
while(l<r && q[r-1].val<=y) r--;
q[r].val=y,q[r++].pos=x;
f[k*v+mo]=q[l].val+k*w;
}
}
}
完全背包問題 - 單調隊列
這裡我們發現，直接把 ⌊ V v i ⌋ \lfloor \frac{V}{v_i} \rfloor ⌊viV⌋ 作為 num \text{num} num 就可以直接通過。這樣我們實作了完全背包和多重背包的 O ( n V ) \mathcal{O}(nV) O(nV).
下面，有了多重背包和完全背包的基礎，我們将來解決更套路性的問題。
混合背包問題
n n n 個物品，背包體積為 V V V，每個物品有 v i v_i vi（價值）和 w i w_i wi（重量），每個物品的個數用符号 t t t 表示。 t = − 1 t=-1 t=−1 表示該物品隻有 1 1 1 個， t = 0 t=0 t=0 表示該物品有無限個， t > 0 t>0 t>0 表示該物品有 t t t 個。求在不超過背包體積的情況下能獲得的最大價值。
n , V , v i , w i ≤ 1 × 1 0 4 n,V,v_i,w_i \leq 1 \times 10^4 n,V,vi,wi≤1×104，時間限制 1 s 1s 1s，空間限制 128 M B 128MB 128MB.
很顯然，我們可以把 01 01 01 背包的物品看成是 num i = 1 \text{num}_i = 1 numi=1 的多重背包物品，完全背包的物品看成是 num i = ⌊ V v i ⌋ \text{num}_i = \lfloor \frac{V}{v_i} \rfloor numi=⌊viV⌋ 的多重背包物品，最後用 O ( n V ) \mathcal{O}(nV) O(nV) 跑一遍多重背包即可。
代碼略。
二維費用背包問題
n n n 個物品，背包體積為 V V V，所能承受的最大重量為 W W W.每個物品有 v i v_i vi（價值）和 w i w_i wi（重量）和 g i g_i gi（體積）。求在不超過背包體積 且 不超過最大載重的情況下能獲得的最大價值。（每個物品隻有 1 1 1 個）
n , V , v i , w i ≤ 5 × 1 0 2 n,V,v_i,w_i \leq 5 \times 10^2 n,V,vi,wi≤5×102，時間限制 1 s 1s 1s，空間限制 128 M B 128MB 128MB.
顯然，我們出現了另一層限制，使得我們無法用 O ( n V ) \mathcal{O}(nV) O(nV) 的時間解決。實際上時間限制也暗示了這一點。我們應該從頭開始，重新推導。其實大多過程是類似的。
基礎推導過程
用 f i , j , k f_{i,j,k} fi,j,k 表示前 i i i 個物品，體積為 j j j，載重為 k k k 的最大價值。
那麼可得：
f i , j , k = max ( f i − 1 , j , k , f i − 1 , j − g i , k − w i + v i ) f_{i,j,k} = \max(f_{i-1,j,k} , f_{i-1,j-g_i , k - w_i} + v_i) fi,j,k=max(fi−1,j,k,fi−1,j−gi,k−wi+vi)
按照這個方式， O ( n V W ) \mathcal{O}(nVW) O(nVW) 足以解決 5 × 1 0 2 5 \times 10^2 5×102 的資料。
僞代碼如下：
for(i=1;i<=n;i++) {
read(g) , read(w) , read(v);
for(j=V;j>=g;j--)
for(k=W;k>=w;k--)
f[j][k]=max(f[j][k],f[j-g][k-w]+v); //降維同 01 背包操作
}
拓展二維背包問題
假設，每個物品有 num i \text{num}_i numi 個，其餘按照二維背包條件不變， 5 × 1 0 2 5 \times 10^2 5×102 仍不變，如何追求一個 O ( n V W ) \mathcal{O}(nVW) O(nVW) 的算法？
實際上單調隊列僅僅是讓我們 完全地把背包的複雜度寄托于物品的個數與限制條件，而與具體數值大小無關，是以單調隊列是可以做到的。
f i , j , k = max l = 0 num i ( f i − 1 , j − l × w i , k − l × g i + l × v i ) f_{i,j,k} = \max_{l=0}^{\text{num}_i} (f_{i-1,j-l \times w_i , k-l \times g_i} + l \times v_i) fi,j,k=l=0maxnumi(fi−1,j−l×wi,k−l×gi+l×vi)
但是，這個你和一維的背包問題比較一下呢：
f i , j = max k = 0 num i ( f i − 1 , j − k × w i + k × v i ) f_{i,j} = \max_{k=0}^{\text{num}_i}(f_{i-1,j-k \times w_i} + k \times v_i) fi,j=k=0maxnumi(fi−1,j−k×wi+k×vi)
一維背包的周期是 w i w_i wi.按照這個說法，二維背包的周期應該是 lcm ( w i , g i ) \operatorname{lcm}(w_i , g_i) lcm(wi,gi)，可以認為是 w i × g i w_i \times g_i wi×gi.
我們需要同時枚舉兩個模數 mo1 \text{mo1} mo1 和 mo2 \text{mo2} mo2，用 mo1 × w i + mo2 \text{mo1} \times w_i + \text{mo2} mo1×wi+mo2 來表示目前節點，然後用單調隊列做即可。
時間複雜度仍然是 O ( n V W ) \mathcal{O}(nVW) O(nVW)，一個道理，每個節點入隊出隊一次。
但是嚴格意義上這個做法是不對的。為什麼呢？
拓展多元背包問題
在拓展二維的基礎上，把每個物品的限制加到 k k k 個，能否做到 O ( n V W ) \mathcal{O}(nVW) O(nVW)？答案是不能。 O ( n V W k ) \mathcal{O}(nVWk) O(nVWk)？這當然可以。
這樣對于 k k k 個限制的相乘，單調隊列的優化已經基本無用。因為在完全随機的， k ≥ 3 k \geq 3 k≥3 的情況之下， k k k 個數的乘積很容易就超過了 max i = 1 n w i \max_{i=1}^n w_i maxi=1nwi 使得優化失敗，無法進行單調隊列操作。
是以， 2 2 2 維也是一個道理，兩個随機的 ≤ 5 × 1 0 2 \leq 5 \times 10^2 ≤5×102 的數相乘超過 5 × 1 0 2 5 \times 10^2 5×102 的機率很大。一旦出現這樣的物品，我們的單調隊列等同于大暴力。而大暴力的複雜度恰恰是 O ( n V W k ) \mathcal{O}(nVWk) O(nVWk)，對于 k k k 個限制還需要進行循環判斷，常數較大。
是以，一般的題目會給定 k k k 的值（并且一般來說 k ≤ 3 k \leq 3 k≤3），把 k k k 當做常數來看！
分組背包問題
n n n 個物品，背包體積為 V V V.每個物品有 v i v_i vi（價值）和 w i w_i wi（重量），隻有 1 1 1 個。
每個物品屬于第 s i s_i si 組。求不超過背包體積 且 每組隻選一個物品的最大價值。
n , V , v i , w i ≤ 1 × 1 0 3 n,V,v_i,w_i \leq 1 \times 10^3 n,V,vi,wi≤1×103，時間限制 1 s 1s 1s，空間限制 128 M B 128MB 128MB.
很明顯，我們應該考慮 dp \text{dp} dp 的推導。用 f k , j f_{k,j} fk,j 表示前 k k k 組物品重量為 j j j 所得的最大價值，易得：
f k , j = max ( f k − 1 , j , max s i = k f k − 1 , j − w i + v i ) f_{k,j} = \max(f_{k-1,j} , \max_{s_i=k} f_{k-1,j-w_i} + v_i) fk,j=max(fk−1,j,si=kmaxfk−1,j−wi+vi)
顯然我們已經得到了一個 O ( n 2 V ) \mathcal{O}(n^2V) O(n2V) 的算法，因為最大組數和 n n n 是同階的，就算成 n n n 吧。
這裡是沒有辦法優化的，因為 w i w_i wi 不連續，單調隊列不行。
僞代碼如下：
for(i=1;i<=n;i++) {
read(s);
for(j=1;j<=s;j++) read(w[j]) , read(v[j]);
for(j=V;j>=0;j--)
for(k=1;k<=s;k++)
if(j>=w[k]) f[j]=max(f[j],f[j-w[k]]+v[k]);
}
有依賴的背包問題
這一道題目将是背包問題中最難的一種。
n n n 個物品，背包體積為 V V V.每個物品有 v i v_i vi（價值）和 w i w_i wi（重量），隻有 1 1 1 個。
每個物品有一個依賴物品 p i p_i pi，如果選了 i i i 物品，則必須選 p i p_i pi 号物品。求不超過背包體積的最大價值。資料保證 每個物品最多依賴于一個物品。（注：是以此類題常常用樹形結構給出，兒子節點和父節點呈依賴關系）
n , V , v i , w i ≤ 1 × 1 0 3 n,V,v_i,w_i \leq 1 \times 10^3 n,V,vi,wi≤1×103，時間限制 1 s 1s 1s，空間限制 128 M B 128MB 128MB.
顯然，這種有依賴的背包并不容易，這和樹形 dp \text{dp} dp 有些類似。簡單的，如果選了 i i i，所有 i i i 的祖先都會被選。
一個非常顯然的思路是，直接把所有子樹的答案計算，合并即可。對于每一個子樹，先不考慮根節點，進行背包，然後最後加上根節點的值即可。（因為根節點無論如何會被選，除非全不選）
代碼略。
泛化物品
背包中比較玄乎的東西，選看選做。
泛化物品的精髓就是，每個物品沒有固定的價值和重量，其價值随着配置設定的重量而變化。簡單的，你用 x x x 的重量去放它，它就會産生 h x h_x hx 的價值貢獻。而 h x h_x hx 的具體計算會給你一個多項式。這是非常好的一類問題。這一類問題的解決相當繁瑣。
比方說吧，若背包容量為 10 10 10， h 1 = 3 x + 2 h_1 = 3x + 2 h1=3x+2，一個物品 h 2 = 2 x + 3 h_2 = 2x+3 h2=2x+3，顯然你直接放 1 1 1 個 h 1 h1 h1，價值就可以達到 32 32 32。這意思不是說貪心可以解決背包，而是這類問題不好解決。
簡單的透露一下，該問題的複雜度應當是 O ( V 2 ) \mathcal{O}(V^2) O(V2)，具體内容可以參考文末的 泛化物品_百度百科.
求方案數 & 具體方案
非常簡單，隻需要再開一個，算出 f f f 後，用 與其同樣維數的 g g g 記錄目前最優解的方案數。隻需要把所有的決策點的 g g g 統計一遍即可得到新的 g g g.
求具體方案也一樣，一般來說會讓你求字典序最小的，那麼你用 與 f f f 同樣維數的 g g g 記錄目前最優解且字典序最小的 那一個編号，這樣就可以解決問題。
如果讓你求全部的最優方案，你需要開一個 vector \text{vector} vector 和 f f f 維數一樣，類似于
vector<int> h[N][M]
的操作，開二維數量個 vector \text{vector} vector，記錄所有答案，最後疊代傳回。
由于方案數的增加呈指數性，一般隻會求特殊的具體方案 / 方案數取模。
附錄：背包問題的搜尋解法
以最簡單的 01 01 01 背包為例，如何用樸素搜尋解決？
大力搜尋
枚舉每個物品選或不選，這樣複雜度是 O ( 2 n ) \mathcal{O}(2^n) O(2n) 的，可以加上剪枝（最主要的：就是目前答案加上所有未選的價值之和也不如之前得到的答案，或者是重量超出限制），但也隻能 勉強 通過 n = 25 n=25 n=25 的資料。
一個基于貪心的優化，将重量小 / 價值大 / 成本效益高的物品先搜尋，會适當提高效率。但是哪怕剪枝到極限，最多也是 n = 26 , 27 n=26,27 n=26,27 的樣子。
NP \text{NP} NP 完全問題
考慮這是一個 NP \text{NP} NP 完全，是以從模闆題出發：
給定集合 S S S，求是否存在集合 X X X 使得 X X X 中的元素之和為 k k k. ∣ S ∣ ≤ 42 |S| \leq 42 ∣S∣≤42.
顯然大力枚舉 2 42 2^{42} 242 是不可能通過的。我們考慮一個簡單的優化。
将 S S S 等分 為兩部分 S 1 S1 S1 和 S 2 S2 S2，然後枚舉 S 1 S1 S1 和 S 2 S2 S2 内所有的可能，并兩兩相加驗證。這樣複雜度是 O ( 2 ⌊ n 2 ⌋ ) \mathcal{O}(2^{\lfloor \frac{n}{2} \rfloor}) O(2⌊2n⌋) 的，可以通過 n = 42 n=42 n=42 的資料。
當然作者可以自行嘗試分更多份，實際上大機率效率不會更高。
折半搜尋
實際上上面解決 NP \text{NP} NP 完全的方法就是折半搜尋的精髓了，對兩邊分别大力搜尋即可實作 O ( 2 ⌊ n 2 ⌋ ) \mathcal{O}(2^{\lfloor \frac{n}{2} \rfloor}) O(2⌊2n⌋) 的複雜度。
搜尋 VS DP \text{VS DP} VS DP
一般來說，設計到多重，完全，肯定是 dp \text{dp} dp.隻有 01 01 01 背包需要進行讨論！
如果 w i , V ≤ 1 0 16 , n ≤ 40 w_i,V \leq 10^{16} , n \leq 40 wi,V≤1016,n≤40，那明顯是折半搜尋。
如果 w i , V , n ≤ 5 × 1 0 3 w_i,V,n \leq 5 \times 10^3 wi,V,n≤5×103，那明顯是 dp \text{dp} dp.
總之，面向資料程式設計是沒有毛病的，具體情況具體分析吧。
課後習題
（ Acwing \text{Acwing} Acwing 上面 9 9 9 道題， 洛谷 \text{洛谷} 洛谷 上 1 1 1 道，一共 10 10 10 道不算多吧）
01 \text{01} 01 背包
完全背包
多重背包 - 單調隊列
多重背包 1 1 1 - 大暴力
多重背包 2 2 2 - 二進制拆分
多重背包 3 3 3 - 單調隊列
混合背包
二維費用背包
分組背包
有依賴的背包
參考資料
泛化物品_百度百科
![[LeetCode]（面試題 17.21）直方圖的水量[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)