動態規劃(Dynamic Programming)

  • 空間換取時間
  • 將運算過且會重複利用到的值存起來

費氏數列

  • \(F_0=0\)
  • \(F_1=1\)
  • \(F_n=F_{n-1}+F_{n-2} (2 \le n)\)

Bottom-up









int x;
long long dp[51];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= 50; i++)
    dp[i] = dp[i - 1] + dp[i - 2];
cin >> x
cout << dp[x];

Top-down














long long dp[51];
int F(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (dp[n] != 0) return dp[n];
    return dp[n] = F(n - 1) + F(n - 2);
}
int main() {
    int x;
    cin >> x;
    cout << F(x);
    return 0;
}

0/1背包問題

將一群物品儘量塞進背包裡面，令背包裡面的物品總價值最高。背包沒有容量限制，無論物品是什麼形狀大小，都能塞進背包；但是背包有重量限制，如果物品太重，就會撐破背包。

範例

物品 價值 體積
A 5 11
B 3 10
C 2 7
體積限制：7
  1. 按照CP值取

範例

物品 價值 體積
A 5 11
B 3 10
C 2 7
體積限制：7
  1. 按照CP值取
  2. 窮舉

優化!

  • 由於每個物品分為取或不取 → 計算次數約為\(2^n\)
  • 動態規劃!!(運算次數為 \(n \cdot w_{max}\))

動態規劃

令陣列\(dp[i][j]\)為在 選取第\(i\)項物品 時，
\(選取物品重量 \le j\) 的最大價值。

  • \(1 \le i \le n\)
  • \(1 \le j \le w_{max}\)

且\(v[i]\)為第\(i\)項的價值，\(w[i]\)為第\(i\)項的重量

經過思考後，可以推出以下轉移式：
\(dp[i][j]=\)
\(\left\{ \begin{array}{l} dp[i-1][j] \text{................................................}(j < w[i])\\ max(dp[i - 1][j], dp[i-1][j-w[i]]+v[i]\text{..}(j \ge w[i])\end{array} \right .\)

解說

\(dp[i][j] = max(dp[i - 1][j],\text{ } dp[i - 1][j - w[i]] + v[i])\)

  1. 不選取： \(dp[i - 1][j]\)代表的是第\(i\)項不選取時 \(總重量 \le j\) 的最大值
  2. 　選取： \(dp[i - 1][j - w[i]] + v[i]\)選取此物品時 \(總重量 \le j\) 的最大值

舉例：\(i=3, j=10, w[i]=6, v[i]=5\)。
則\(i-1=2, \text{ }j-w[i]=4\)。
\(dp[i-1][j-w[i]]+v[i] = dp[2][4]+5\)。

ZeroJudge d637

第一行有正整數\(n(1 < n \le 10000)\)表有n顆鴨飼料
接下來的\(n\)行，每行有\(ab\)兩個正整數，
\(a\)代表這顆鴨飼料的體積，\(b\)代表飽足感\((1 \le a \le 100 , 1 \le b \le 5000)\)
並且鴨子最多可以吃滿100體積的飼料。
請輸出最大飽足感為何。

  • 範例輸入：
6
10 8
25 25
65 75
25 29
25 17
15 20
  • 範例輸出：
112 (選取第1,3,4項)

程式碼



















#include <iostream>
using namespace std;
const int maxn = 10000 + 1;
const int w_max = 100;
int dp[maxn][w_max + 1], w[maxn], v[maxn], n, ans;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < w[i]; j++)
            dp[i][j] = dp[i - 1][j];
        for (int j = w[i]; j <= w_max; j++)
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
    }
    cout << dp[n][w_max];
    return 0;
}

補充

根據以上程式碼，可以透過「滾動」的技巧來降低陣列大小，因只會存取到\(dp[i]和dp[i-1]\)，更以前的值不需要
則可令
\(\left\{ \begin{array}{l} dp[i]=dp[i\text{%}2]=dp[i\text{&}1]\\ dp[i-1]=dp[(i-1) \text{%}2] =dp[!(i\text{&}1)]\end{array} \right .\)

則程式碼可變成如下：




















#include <iostream>
using namespace std;
const int maxn = 10000 + 1;
const int w_max = 100;
int dp[2][w_max + 1], w[maxn], v[maxn], n, ans;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++) {
        bool now = i & 1; bool prev = !now;
        for (int j = 1; j < w[i]; j++)
            dp[now][j] = dp[prev][j];
        for (int j = w[i]; j <= w_max; j++)
            dp[now][j] = max(dp[prev][j], dp[prev][j - w[i]] + v[i]);
    }
    cout << dp[n & 1][w_max];
    return 0;
}
Select a repo