淺談背包問題 (0/1 Knapsack Problem) 優化那些事

contents

1. 1. 輸入格式
2. 2. 輸出格式
3. 3. 範例輸入 1
4. 4. 範例輸出 1
5. 5. 範例輸入 2
6. 6. 範例輸出 2
7. 7. Solution
   1. 7.1. Branch-and-bound
      1. 7.1.1. 結論
   2. 7.2. Dynamic Programming
      1. 7.2.1. 前言
      2. 7.2.2. 優化初夜
      3. 7.2.3. 優化二夜

收錄於 批改娘 20005. 0/1 Knapsack Problem。之所以有機會談到這個問題，其原因於早期的背包問題，大多都是用 branch-and-bound 算法來完成，也因此學弟課程出了這一份作業，大部分的測資，使用 branch-and-bound 能跑得比一般記憶體化 DP 快上非常多。當然，作為一個 Morris(?) 怎能允許這樣的事情發生。

現在回顧一下背包問題的模型吧！

輸入格式

每組測資第一行包含兩個正整數，分別代表背包大小 $M$ ($\leq 5×10^6$) 和物品個數 $N$ ($\leq 1000$)，下一行開始每行包含兩個正整數，分別代表物品價值 $P_i$ ($\leq 10^5$)和物品重量 $W_i$ ($ \leq 10^5$)。

輸出格式

對於每組測資，請輸出最大收益。

範例輸入 1

50 7
70 31
20 10
39 20
37 19
7 4
5 3
10 6

範例輸出 1

107

範例輸入 2

170 7
442 41
525 50
511 49
593 59
546 55
564 57
617 60

範例輸出 2

1735

Solution

Branch-and-bound

bound knapscak problem 古耕竹同學提供

如果物品可以被切割，那麼可以利用物品的 CP 值 ($\textit{cp}_i = p_i/w_i$)排序，使用貪心算法在 $O(N \log N)$ 找到最佳解。然而，背包問題在於物品只能挑或不挑，一旦無法切割物品，那麼貪心算法無法將剩餘的部分填滿，進而可能產生更好的一組解填滿剩餘部分。

想要更快嗎？多看論文且實作它吧！

branch-and-bound 基本核心操作為

• 按照 CP 值由大到小排序
• 貪心法最佳解 $\textit{bound}$
• 進行深度優先搜索，優先挑 CP 值大的入選
  • 當前挑選方案最佳解 $g$ + 剩餘物品使用貪心法最佳解 $g$ 小於等於當前最佳解 $\textit{bound}$，則退出搜索。
  • 更新 $\textit{bound} = \max(\textit{bound}, g)$
  • 選擇加入 或 不加入 (註：學弟說我的某些測資，通通優先不選可以快個數十倍)

參考代碼

#include <bits/stdc++.h>
using namespace std;

struct Item {
    int v, w;
    double cp() {
        return (double) v / w;
    }
};

int cmpCP(Item a, Item b) {
    double cpA = a.cp();
    double cpB = b.cp();
    if (cpA == cpB)
        return a.w > b.w;
    return cpA > cpB;
}

int n, m;
int ret = 0;
Item items[1005];
int prefixW[1005];
int prefixV[1005];
 
int h(int i, int w, int b, int &j, int &f) {
    int fw = i == 0 ? w : (w + prefixW[i-1]);
    for (j = max(b, i); j < n && prefixW[j] <= fw; j++);
    if (j >= n) {
        return prefixV[n-1];
    }
    int v = 0;
    f = 0;
    v += prefixV[j-1] - (i == 0 ? 0 : prefixV[i-1]);
    w -= prefixW[j-1] - (i == 0 ? 0 : prefixW[i-1]);
    if (w != 0) {
        f = 1;
        float k = (float) w / items[j].w;
        w -= k * items[j].w;
        v += k * items[j].v;
    }
    return v;
}
 
int greedy(int w) {
    int v = 0;
    for(int i = 0; i < n; i++)  {
        if (w >= items[i].w){
            w -= items[i].w;
            v += items[i].v;
        } else {
            return v;
        }
    }
    return v;
}

void dfs(int i, int w, int v, int b) {
    if (i >= n) {
        ret = max(ret, v);
        return;
    }
    int j = n, f;
    int hv = v + h(i, w, b, j, f);
    if (hv <= ret)
        return;
    if (f == 0) {
        ret = max(ret, hv);
        return;
    }
    if (w >= items[i].w)
        dfs(i + 1, w - items[i].w, v + items[i].v, j);
    dfs(i + 1, w, v, j);
    return;
}
 
int main() {
    while (scanf("%d %d", &m, &n) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d %d", &items[i].v, &items[i].w);
        stable_sort(items, items+n, cmpCP);
        for (int i = 0, w = 0, v = 0; i < n; i++) {
            w += items[i].w;
            v += items[i].v;
            prefixW[i] = w;
            prefixV[i] = v;
        }
        ret = greedy(m);
        dfs(0, m, 0, 0);
        printf("%d\n", ret);
    }
    return 0;
}

結論

branch-and-bound 空間複雜度只跟 $N$ 有關，使用記憶體空間小，相較於記憶化搜索有較少的 cache miss，速度取決於搜索順序。對於同一 CP 的等價處理薄弱，一遇到這種情況，搜尋時間瞬間指數次方上去，可以等個昏天暗地。

Dynamic Programming

前言

請不要忘記背包問題屬於 NP-Complete，我們能做的事情只能優化計算，最慘的情況仍要面對，優化常數是可以努力的方向，讓我們嘗試變得更快吧。

基礎寫法解說請參考 DJWS - Bounded Knapsack Problem 的說明。

從定義上，我們通常會宣告 dp[i][j] 表示放入前 $i$ 個物品時，總共最多為 $j$ 的最大價值為何。這樣空間宣告使用 $\mathcal{O}(NW)$。在實作上，我們可以藉由運算順序將空間降為 $\mathcal{O}(W)$。因此，寫出以下代碼並不難

int dp[MAXW];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++)
    for (int j = W; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);

優化初夜

從實際運行上，我們可以發現每次跑 $\mathcal{\theta}(W)$ 非常浪費，只需要跑 $\min(W, \sum w_i)$ 即可。因此，第一份計算量優化如下

int dp[MAXW];
memset(dp, 0, sizeof(dp));
for (int i = 0, sum = 0; i < N; i++) {
    sum += w[i];
    for (int j = min(W, sum); j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}

計算邊界優化通常可以達到 2x 加速

如此一來，在數量多權重小時，剛啟動的效能時可以賺到非常多。然而，不乏第一次就給權重的大的，目標最小化 $\sum \text{sum}_i$，從數學觀念很明顯地瞭解，只要一開始將權重 $w_i$ 由小到大排序即可，這樣能保證最小化計算量！

int dp[MAXW];
memset(dp, 0, sizeof(dp));
sort (w, v) by w
for (int i = 0, sum = 0; i < N; i++) {
    sum += w[i];
    for (int j = min(W, sum); j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}

數學使得我們更進一步，達到 1.5x 加速

優化二夜

經由平行的訓練，也許我們可以更往上一層優化。

接下來，打算把物品拆成兩堆，再利用優化初夜學到的技巧，就能引爆更多計算邊界優化。如果拆成三堆以上，合併操作變得相當複雜，當只有兩堆時，保證合併效能一定在 $\mathcal{\theta}(W)$ 完成。

如何合併兩堆的計算結果，假設 dp1[i] 表示其中一堆重量小於等於 $i$ 的最佳解，同理 dp2[j] 的計算結果。

當要湊出重量為 $W$ 的最佳解時，窮舉其中一堆的重量 $i$ 維護其中一堆的前綴最大值 $j$，相當於使用掃描線算法在線性時間內合併。合併操作如下：

int ret = 0;
for (int i = 0, j = W, mx = 0; i <= W; i++, j--) {
    mx = max(mx, dp2[i]);
    ret = max(ret, dp1[j] + mx);
}

Divide-and-Conquer，使得我們更快再更快！達到 1.5 加速

然而，優化問題將轉移到最佳分堆策略，好的分堆策略將使得計算量下降更多。目標分兩堆，使得 $\sum \text{sum1}_i + \sum \text{sum2}_i$ 最小化。明顯地，由小到大排序物品重量，依序將物品放到總和最小的那一堆即可。最後，我們整合每一夜的結果如下：

一個好的分堆，達到 1.2x 加速

相信在不久之後，還有更好的優化策略，也許不是延伸，而是全新的面貌。

#include <bits/stdc++.h>
using namespace std;

namespace {

    static const int MAXW = 5000005;
    static const int MAXN = 1005;

    static void run(int A[][2], int dp[], int W, int N) {
        for (int i = 0, sum = 0; i < N; i++) {
            int w = A[i][0], v = A[i][1];
            for (int j = min(W, sum + w); j >= w; j--)
                dp[j] = max(dp[j], dp[j-w]+v);
            sum += w;
        }
    }

    static int knapsack(int C[][2], int N, int W) {
        vector< pair<int, int> > A;
        for (int i = 0; i < N; i++)
            A.push_back(make_pair(C[i][0], C[i][1]));
        N = A.size();
        assert(N < MAXN);
        static int dp1[MAXW+1], dp2[MAXW+1];
        int Ar[2][MAXN][2], ArN[2] = {};
        memset(dp1, 0, sizeof(dp1[0])*(W+1));
        memset(dp2, 0, sizeof(dp2[0])*(W+1));
        sort(A.begin(), A.end());
        int sum[2] = {};
        for (int i = 0; i < N; i++) {
            int ch = sum[1] < sum[0];
            Ar[ch][ArN[ch]][0] = A[i].first;
            Ar[ch][ArN[ch]][1] = A[i].second;
            ArN[ch]++;
            sum[ch] += A[i].first;
        }

        run(Ar[0], dp1, W, ArN[0]);
        run(Ar[1], dp2, W, ArN[1]);

        int ret = 0;
        for (int i = 0, j = W, mx = 0; i <= W; i++, j--) {
            mx = max(mx, dp2[i]);
            ret = max(ret, dp1[j] + mx);
        }
        return ret;
    }
}

int main() {
    int W, N, C[MAXN][2];
    while (scanf("%d %d", &W, &N) == 2) {
        for (int i = 0; i < N; i++)
            assert(scanf("%d %d", &C[i][1], &C[i][0]) == 2);
        printf("%d\n", knapsack(C, N, W));
    }
    return 0;
}