昨天說了基本的動態規劃，今天來看看其中常見的變種。

背包問題

背包問題的基本問題：

一個容量有限的背包容量為 V ，眼前有 N 種物品，每種物品都有各自的體積與價值v。在不超過背包容量的前提下，如何挑選物品，才能讓背包裡物品的總價值最大化。

0-1 背包問題

限制:每種物品只有1件
這個題目的意思就是只有選或不選，所以就是定義 dp[i][j] 為前 i 個物品，在背包容量為 j 時能拿到的最高價值。
寫法：

// 傳入參數：背包總容量 V、物品數量 N、體積 W、價值 v
int knapsack01_2D_split(int V, int N, const vector<int>& W, const vector<int>& v) {
    vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0));
    
    for (int i = 1; i <= N; ++i) {
        int w = W[i - 1];
        int val = v[i - 1]; 
        
        // 轉移方程: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + val)
        for (int j = 0; j <= V; ++j) {
            if (j < w) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + val);
            }
        }
    }
    return dp[N][V];
}

上面解法的空間複雜度是O(VN)
我們可以發現這題實際上只需要定義 dp[i] 為當體積為i時的最高價值
寫法：

// 傳入參數：背包總容量 V、物品數量 N、體積 W、價值 v
int knapsack01_1D_split(int V, int N, const vector<int>& W, const vector<int>& v) {
    vector<int> dp(V + 1, 0);
    
    for (int i = 0; i < N; ++i) {
        int w = W[i];
        int val = v[i]; 
//      這裡使用迴圈來減少空間使用        
        for (int j = V; j >= w; --j) {//倒序以避免重複計數
            dp[j] = max(dp[j], dp[j - w] + val);
        }
    }
    return dp[V];
}

這樣就把空間複雜度降至O(V)了

完全背包問題

限制：每種物品無限多個
這題就是要讓迴圈正序來更新dp，就能夠模擬出無限多個的辦法

// weights: 物品重量陣列, values: 物品價值陣列, W: 背包最大容量
vector<int> dp(V + 1, 0);

for (int i = 0; i < N; i++) {           // 遍歷物品
    for (int j = w[i]; j <= V; j++) { // 正序遍歷背包容量
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

多重背包問題

限制：每種物品都有限定數量
本質上可以當1-0背包問題來解

// 傳入參數：背包總容量 V、物品數量 N、體積 W、價值 v、個數 C
int knapsack_bounded_naive(int V, int N, const vector<int>& W, const vector<int>& v, const vector<int>& C) {
    vector<int> new_W, new_v;
    for (int i = 0; i < N; ++i) {
        for (int c = 0; c < C[i]; ++c) {
            new_W.push_back(W[i]);
            new_v.push_back(v[i]);
        }
    }
    vector<int> dp(V + 1, 0);
    for (size_t i = 0; i < new_W.size(); ++i) {
        for (int j = V; j >= new_W[i]; --j) {
            dp[j] = max(dp[j], dp[j - new_W[i]] + new_v[i]);
        }
    }
    return dp[V];
}

但上方的時間複雜度為O(VC)
我們可以以二進位拆分優化來使時間複雜度變為O(VlogC)

// 傳入參數：背包總容量 V、物品數量 N、體積 W、價值 v、個數 C
int knapsack_bounded_optimized(int V, int N, const vector<int>& W, const vector<int>& v, const vector<int>& C) {
    vector<int> new_W, new_v;
    for (int i = 0; i < N; ++i) {
        int c = C[i];
        int k = 1;
        while (c >= k) {
            new_W.push_back(k * W[i]);
            new_v.push_back(k * v[i]);
            c -= k;
            k *= 2;
        }
        if (c > 0) {
            new_W.push_back(c * W[i]);
            new_v.push_back(c * v[i]);
        }
    }
    vector<int> dp(V + 1, 0);
    for (size_t i = 0; i < new_W.size(); ++i) {
        for (int j = V; j >= new_W[i]; --j) {
            dp[j] = max(dp[j], dp[j - new_W[i]] + new_v[i]);
        }
    }
    return dp[V];
}

今天說了點dp經典背包問題及其變種
明天將說說bitmask dp