# 動態規劃 --- ## 基本概念 ---- - 動態規劃又稱dp(dynamic programming) - 適用於能將問題拆成子問題的狀況 - 問題通常會有狀態，且狀態可轉移 - 直接看一個經典的例子吧<!-- .element: class="fragment" data-fragment-index="1" --> ---- - ~~背包問題~~ - 費氏數列 - $$ a_i=\left\{ \begin{aligned} 1 && i=1,2 \\ a_{i-2}+a_{i-1} && i\geq3 \\ \end{aligned} \right. $$ - 此時費氏數列的每一項都是一個狀態<!-- .element: class="fragment" data-fragment-index="1" --> - 這個狀態需要由它的前兩項轉移(即前兩項的和)<!-- .element: class="fragment" data-fragment-index="1" --> ---- - 以費氏數列為例，求第$n$項可以被切成兩個小問題：求第$n-1$項和第$n-2$項 - 同樣的，小問題也可以在繼續被切割 - 而在利用小問題求答案時，我們能夠列出轉移式(前兩項相加) - 因此，這是一個能使用動態規劃解決的問題 - 當然這題其實不需要動態規劃也能做<!-- .element: class="fragment" data-fragment-index="1" --> ---- - 總之，動態規劃的重點就是:**<font color="#f00">同樣的問題不要做第二次</font>** - 以費氏數列為例，可以開個陣列記錄以前算過的結果 - 這樣之後需要時就可以直接取來用 - 時間就會超快(〃'▽'〃)<!-- .element: class="fragment" data-fragment-index="1" --> --- ## 基礎應用 ---- - 題目來源2020IONCamp World Final div.1pA div2.pD： - 今年暑假有$n$天，你決定~~當個爆肝仔~~每天打工 - 你每天都可以決定要去A商店或B商店打工 - 第$i$天在A商店打工會得到$a_i$元，在B商店則會得到$b_i$元 - 但是如果你今天在A或B商店打工，隔天卻跑去另一家商店打工，你會被罰款$k$元 - 請問你這個暑假最多能賺多少錢？ - $(1\leq n\leq10^5,1\leq k,a_i,b_i\leq10^4)$ ---- - 每天都看換打工地點還是不換賺比較多 - 感覺很合理? - WA<!-- .element: class="fragment" data-fragment-index="1" --> - $n=3,k=4$.<!-- .element: class="fragment" data-fragment-index="2" --> - $a={1,7,1}$.<!-- .element: class="fragment" data-fragment-index="2" --> - $b={3,2,6}$.<!-- .element: class="fragment" data-fragment-index="2" --> - 最大收益為11<!-- .element: class="fragment" data-fragment-index="3" --> - 依照策略你會想在第2天繳罰款去A商店打工，可是這樣無法獲得最大收益<!-- .element: class="fragment" data-fragment-index="3" --> ---- #### \動態規劃/ - 狀態-如果第$i$天在A商店打工的話，前$i$天最多賺多少($dp_a[i]$)<!-- .element: class="fragment" data-fragment-index="1" --> - 依照同樣的概念，維護一個<!-- .element: class="fragment" data-fragment-index="1" -->$dp_b[i]$<!-- .element: class="fragment" data-fragment-index="1" --> - 轉移-前一天在那裡打工會比較賺<!-- .element: class="fragment" data-fragment-index="2" --> - $dp_a[i]=max(dp_a[i-1],dp_b[i-1]-k)+a_i$<!-- .element: class="fragment" data-fragment-index="2" --> - 答案就是看你最後一天在哪打工賺比較多<!-- .element: class="fragment" data-fragment-index="3" --> - $ans=max(dp_a[n],dp_b[n])$.<!-- .element: class="fragment" data-fragment-index="3" --> --- ## 進階應用 ---- ### 真·經典題-01背包 ###### 沒事還沒輪到你邱翊均 ---- - 有$n$個物品，每個物品有它的體積$w_i$及價值$v_i$ - 你有一個容積為$m$的背包 - 請問你最多可以在背包裡裝下多少價值？ - $(1\leq n,m,w_i\leq5000，1\leq v_i\leq10^9)$ ---- - 先拿CP值最高的? <font color="#f00">WA</font> - 多枚舉幾次? <font color="#f00">TLE</font> - 回到一開始提到的狀態及轉移，你想到了什麼? ---- - 先忘記物品有價值 - 如果今天只有一個物體積為$a$ ($\leq m$)，那背包能裝那些可能的重量？ - 0(什麼都不裝)、$a$(裝了那個物品)(兩種可能)<!-- .element: class="fragment" data-fragment-index="1" --> - 如果再多一個物品體積為$b$ ($a+b\leq m$)呢？<!-- .element: class="fragment" data-fragment-index="2" --> - 0、$a$、$b$、$a+b$(四種可能)<!-- .element: class="fragment" data-fragment-index="3" --> - 因為背包空間只有$m$，最多出現$m+1$種可能的負重<!-- .element: class="fragment" data-fragment-index="4" --> - 回來想想物品有價值吧<!-- .element: class="fragment" data-fragment-index="4" --> ---- - 如果有兩種方式能夠裝下總負重為$k$的物品，優先選價值較高的 - 在記錄負重可能時，同時記錄此負重方法的價值<!-- .element: class="fragment" data-fragment-index="1" --> - 如果出現了兩種負重可能有同樣的負重，利用價值來更新<!-- .element: class="fragment" data-fragment-index="1" --> - 講白一點，就是湊到重量為$k$的方法時，記得更新負重為$k$時的最大價值<!-- .element: class="fragment" data-fragment-index="2" --> - 有聞到動態規劃了嗎?<!-- .element: class="fragment" data-fragment-index="3" --> ---- - 狀態-如果裝體積和為$x$的東西，最多能裝多少價值($dp[i]$)<!-- .element: class="fragment" data-fragment-index="1" --> - 轉移-如果這個容積包括一個體積為$w$，價為$v$的東西，會不會有更大價值<!-- .element: class="fragment" data-fragment-index="2" --> - $dp[i]=max(dp[i],dp[i-w]+v)$，<!-- .element: class="fragment" data-fragment-index="2" -->注意$i-w\geq0$<!-- .element: class="fragment" data-fragment-index="2" --> ---- - 注意一個物品被重複拿取的狀況 - 不行嗎? (~~會WA~~)<!-- .element: class="fragment" data-fragment-index="1" --> - 廢話這是01背包問題(0:不拿、1:拿)<!-- .element: class="fragment" data-fragment-index="2" --> - 最佳情況不一定是把背包裝滿!<!-- .element: class="fragment" data-fragment-index="3" --> ``` cout<<dp[m]<<'\n'; ``` <!-- .element: class="fragment" data-fragment-index="4" --> - 要取整個$dp$陣列的最大值 - 當然你也可以用其他方法改進 <!-- .element: class="fragment" data-fragment-index="5" --> ---- - dp的題目很常出現，只是通常會帶點包裝 - 有些則是需要用一些很毒瘤的優化 <!-- .element: class="fragment" data-fragment-index="1" --> - 「毒瘤的優化」： - 快速莫比烏斯變換(for S.O.S.dp) - 單調隊列優化 - 斜率優化 - aliens優化 a.k.a WQS二分搜 ( 有興趣可以去查查...加油 (• ̀ω•́ )✧ ) <!-- .element: class="fragment" data-fragment-index="2" --> ---- ### 接下來的題目我就不打題解ㄌ ### 大家自己想想看吧 ###### @邱翊均 ---- ### 經典(?)題目 AI-666 - 來源：2017全國賽 - AI-666幫你預測了未來$n$天的股價(第$i$天$a_i$) - 你最多可以買入賣出各$k$次(買入後的操作必為賣出，反之亦然) - 問最大獲利? - $(1\leq k\leq n\leq2\times10^6,1\leq a_i\leq10^7)$ ---- ### 經典(?)題目 背包問題 - 來源：某年NPSC決賽 - 有$n$個物品，每個物品有它的體積$w_i$及價值$v_i$ - 對於第$i$個每個物品，你可以花$c_i$的價值將它切割成任意$x$，$x\leq w_i$ - 切割後，物品所剩價格為$v_i\times \frac{x}{w_i}$ - 你有一個容積為$m$的背包 - 請問你最多可以在背包裡裝下多少價值？ - $(1\leq n,m,w_i\leq5000，1\leq c_i,v_i\leq10^9)$ --- # 課程就到這邊 #### 準備玩rpgㄅ ---