批改娘 10094. Fast 0/1 Knapsack Problem

1. 題目描述
2. 輸入格式
3. 輸出格式
4. 範例輸入
5. 範例輸出
6. Solution
1. 6.1. 滾動數組
2. 6.2. 分組合併

題目描述

有 $N$ 個重量和價值分別為 $W_i, V_i$ 的物品，現在要從這些物品中選出總重量不超過 $M$ 的物品，求所有挑選方案中的總價值最大值為何。

輸入格式

輸入只有一組測資，第一行會有兩個整數 $N, M$ 分別表示物品數量和背包能容大的最大重量 $M$。接下來會有 $N$ 行，第 $i$ 行上會有兩個整數 $W_i, V_i$，分別為物品 $i$ 的重量和價值。

$1 \le N \le 10000$
$1 \le M \le 1000000$
$1 \le W_i, \; V_i \le 100000$

輸出格式

輸出一行整數，挑選方案中的最大價值 $B$。

範例輸入

範例輸出

Solution

遞迴公式

$$\begin{align*} f(i, j) = \max(f(i-1, j-w)+v, f(i-1, j)) \end{align*}$$

最單純採用滾動數組完成，也就是所謂的 double buffer 的技巧，可以大幅度節省記憶體，但先決條件是他們的相依關係必須獨立。

在平行處理上的另一種解法，就是分成前 $N/2$ 個物品和後 $N/2$ 物品分開計算，之後再藉由 $\mathcal{O}(M)$ 合併答案，由於算法的限制，最多拆分兩組。而不像滾動數組的平行於最內層的迴圈，平行度有限，但在較少核心的處理上非常快速，其一原因是空間使用比較有效率。

Server (32 cores)
- 分組合併: Accepted (768 ms, 8320 KB)
- 滾動數組: Accepted (380 ms, 8 MB)
PC (4 cores)
- 分組合併: 600ms
- 滾動數組: 900ms

滾動數組

#include <stdio.h>
#include <stdlib.h>
 
#define MAXM 1000005
#define MAXN 10005
int dp[2][MAXM];
int W[MAXN], V[MAXN];
#define max(a, b) (a > b ? a : b)
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 0; i < N; i++)
            scanf("%d %d", &W[i], &V[i]);
        memset(dp, 0, sizeof(dp));
 
        int p = 0;
        for (int i = 0; i < N; i++) {
            int q = 1 - p;
            #pragma omp parallel
            {
                int pp = p, qq = q;
                int v = V[i], w = W[i];
                #pragma omp for
                for (int i = w; i <= M; i++)
                    dp[qq][i] = max(dp[pp][i-w]+v, dp[pp][i]);
                #pragma omp for
                for (int i = 0; i < w; i++)
                    dp[qq][i] = dp[pp][i];
            }
            p = 1 - p;
        }
 
        printf("%d\n", dp[p][M]);
    }
    return 0;
}

分組合併

#include <stdio.h>
#include <stdlib.h>
 
static inline int max(int a, int b) {
    return a > b ? a : b;
}
void subKnapsack(int n, int m, int w[], int v[], int dp[]) {
    memset(dp, 0, sizeof(dp[0]) * (m+1));
    for (int i = 0; i < n; i++) {
        int vv = v[i], ww = w[i];
        for (int j = m; j >= ww; j--)
            dp[j] = max(dp[j], dp[j-ww]+vv);
    }
}
#define MAXM 1000005
#define MAXN 100005
int W[MAXN], V[MAXN];
int dp[2][MAXM];
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 0; i < N; i++)
            scanf("%d %d", &W[i], &V[i]);
        memset(dp, 0, sizeof(dp));
 
        #pragma omp parallel sections
        {
            #pragma omp section
            subKnapsack(N/2, M, W, V, dp[0]);
            #pragma omp section
            subKnapsack(N-N/2, M, W+N/2, V+N/2, dp[1]);
        }
 
        int ret = 0;
        for (int i = M, j = 0, mx = 0; i >= 0; i--) {
            mx = max(mx, dp[1][j]), j++;
            ret = max(ret, dp[0][i] + mx);
        }
        printf("%d\n", ret);
    }
    return 0;
}

Morris' Blog