演算法知識 - 動態規劃 Dynamic programming

動態規劃 Dynamic programming 介紹

動態規劃用在需要狀態轉移的題目上，例如說 $y = 2x+1$，那麼在計算出 y 之前就必須要有 x，否則 y 沒有辦法產生一個自然數。

動態規劃最好的理解方式就是，我們將某些變數的所有可能都列舉出來，並根據我們之前的紀錄，並透過遞迴關係式找出答案。
舉例：$y = 2x+1$，我們可以將產生出來的 y，再帶入 x，想請問 y 等於 15 有幾種組合可以產生。

• 遞迴關係式就是 $y = 2x+1$
• 我們可以設定一個陣列 dp[x(0~15)] = x 組合的數量
• 現在我們可以做一個迴圈如下

1
2
3

for(int i = 0; i <= 15; i++){
    dp[2*i+1] = dp[i] + 1;
}

• 你跟我說這很像遞迴？對！他就是遞迴的有效率版，浪費記憶體版XD。

下面我們來聊聊一些常用的 dp 問題

01 背包問題 Knapsack Problem

你是一個水果批發商，你的卡車容量最多只能載 G 箱，你有很多種水果，他們在市場的賣出價為 S、買入價為 F、並且我們的預算只有 C，我們的目標是期望所有水果賣出價最高、C 最低。

並且水果每種只能買一箱，因為我們批發的水果都是高級水果，人人搶著要。

解法

通常遇到這種問題，就是使用這種解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

memset(dp, INF, sizeof(dp));
memset(dp[0], 0, sizeof(dp[0])); //車子是 0 貨箱時，一定沒辦法買水果，因此最低價都是 0

for(int i = 0; i <= 每種水果; i++){
    for(int j = 0; j <= 卡車容量; j++){
        for(int k = 0; k <= 預算; k++){
            //主要是我們假設卡車容量有 1~G，
            //總預算有 1~n 
            //我們透過紀錄，在卡車容量是 G-1 的情況，卡車現在預算 - 這種水果預算時，
            //有沒有比現在的 dp[卡車容量][預算] 來得小，有就替換
            dp[j][k] = min(dp[j][k], dp[j-1][cost - 水果買入價] + 水果賣出價 )
        }
    }
}

//想要找到最高的預算就是
cout << dp[卡車容量][預算];