動態規劃(Dynamic Programming)

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;
}

範例

1. 按照CP值取

範例

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;
}