PTT推薦

Re: [問卦] 學會DP可以領多少?

看板Gossiping標題Re: [問卦] 學會DP可以領多少?作者
bluebluelan
(鈴谷のあまあま写生管理)
時間推噓 3 推:3 噓:0 →:3

安安 DP只是一種工具

也不是說遞迴的值存起來 多的是跟遞迴沒關係的DP解法

DP會說到遞迴基本上都是用費伯納契數列的入門

但有其他的像是01背包問題 就是一個DP比較泛用的例子


DP的重點在於

1. dp[i]定義

2. 狀態推導


費伯納契的dp[i]定義就是 費伯納契數列的第i+1個數

1, 1, 2, 3, 5, 8.....


因為費伯納契數列的數 就是該數前兩位相加 所以費伯納契dp[i]的狀態推導就是

dp[0] = 1, dp[1] = 1, 那dp[2] = dp[0]+dp[1] = 2

i>=2 dp[i] = dp[i-1] + dp[i-2]


dp[2] 為 費伯納契數列的第三個數 dp[3] 為第四個 依此列推



任何dp問題 只要把這兩個東西找出來 大概90%就完成了


像是01背包問題 dp[i] 就是 當背包空間為i的時候 背包內物品價值最高為多少

他的狀態推導 就是 dp[i] = max(dp[i], dp[i - volume[j]] + value[j]);

這個狀態推導有點跳 但意思就是說 背包空間為i 裝物品j的價值與不裝哪個高


舉個例子 假設我們 背包空間為50公升

分別有三個物品 每個物品只能放一次

物品A 20公升 價值為$10

物品B 30公升 價值為$5

物品C 50公升 價值為$20

那要怎麼裝 背包物品的價格會最高?


回到我們剛剛的狀態推導

dp[i] = max(dp[i], dp[i - volume[j]] + value[j]);


這邊我有點偷懶 用一維矩陣來算dp

所以需要一個小技巧就是從背包空間大到小 01背包問題因為物品只能被放一次

我們要從dp[50]開始

dp[50] = max(dp[50], dp[50-物品C體積]+物品C價值) = 20

只放物品C價值$20 因為物品C空間需要50 所以低於50我們都不用算了

break;


再來是跟放物品B比

dp[50] = max(dp[50]=20, dp[50-物品B體積]+物品B價值) 還是 只放物品C高

同時得到一個有意義的值 dp[49~30] 都是等於 $5

等等我們會用到


再來是跟放物品A比

dp[50] = max(dp[50]=20, dp[50-物品A體積]+物品A價值) 還是 只放物品C高

有趣的是這邊 dp[50] = max(dp[50], dp[50-20]+物品A價值)

dp[30]剛剛我們算過 是$5 就是只放物品B的價值 背包空間還有20 還夠放個物品A

那dp[30]+物品A的價值 就是 物品A+B的價值 = $15 還是比只放物品C低


最後我們得到 dp[50]當背包空間為50 物品價值最高為$20


這個簡單的例子 你用肉眼看就知道 只塞物品C價值最高 A+B也沒C高

但是當今天背包空間超大 物品幾千個 你人肉眼看不出來 算個老半天也算不出來


但是用一樣的dp[i]定義 一樣的狀態推導 背包從大到小


寫個小程式就能把答案算出來了



TLDR

DP只有兩個重點

1. dp[i]定義

2. 狀態推導



本巨巨祝福大家都能開開心心 輕輕鬆鬆學DP 謝謝大家

※ 引述《Nigger5566 (尼哥56)》之銘言:
: DP, Dynamic Programming 動態規劃
: 演算法的一個章節
: 大概就是把遞迴的值存起來不用重複迴
: 用嘴巴講的話滿簡單的
: 學會了DP可以幹嘛
: 能去Google上班嗎
: 有沒有八卦
:

--

※ PTT 留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.207.8.217 (美國)
PTT 網址

Replly 06/08 13:00好慘 幫你推一個

NCUking 06/08 13:02我只會Hello world

Nigger5566 06/08 13:03我懂背包問題啊,對我來說也只是遞迴

Nigger5566 06/08 13:03的變形

milkBK 06/08 13:08恩恩 跟我想的一樣

c4658860 06/08 13:09謝謝 長知識了 優文