POJ 3624 Charm Bracelet - 01 背包滾動數組優化

題目

N ≤ 3403 件物品，背包容量 M ≤ 12880。每件有重量 w[i]、價值 d[i]。求最大價值。標準 01 背包，但 N×M ≈ 4.4×10^7，二維數組 dp[N][M] 內存超限 (≈ 170MB)。

兩種空間優化方案

方案 1：滾動數組 (兩行交替)

vector<vector<int>> dp(2, vector<int>(M+1));
bool cur = 0;
for (int i = 1; i <= N; i++) {
    for (int j = 0; j < w[i]; j++) dp[cur][j] = dp[!cur][j];
    for (int j = w[i]; j <= M; j++)
        dp[cur][j] = max(dp[!cur][j], dp[!cur][j-w[i]] + d[i]);
    cur = !cur;
}
return dp[!cur][M];

方案 2：一維逆序 (推薦，更簡潔)

int dp[M+1] = {0};
for (int i = 1; i <= N; i++)
    for (int j = M; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j-w[i]] + d[i]);
return dp[M];

原理解析

• 01 背包轉移只依賴 i-1 行數據
• 逆序遍歷 j 保證讀到的 dp[j-w[i]] 仍是上一輪 (i-1) 的值
• 正序會導致同一物品被重複使用 (變成完全背包)

完整代碼

#include <cstdio> #include <algorithm> #include <vector>
using namespace std;
const int MAX_W = 12881, MAX_N = 3403;
int N, M, w[MAX_N], d[MAX_N], dp[MAX_W];

int main() {
    while (scanf("%d%d", &N, &M) != EOF) {
        for (int i = 1; i <= N; i++) scanf("%d%d", &w[i], &d[i]);
        fill(dp, dp+M+1, 0);
        for (int i = 1; i <= N; i++)
            for (int j = M; j >= w[i]; j--)
                dp[j] = max(dp[j], dp[j-w[i]] + d[i]);
        printf("%d\n", dp[M]);
    }
    return 0;
}