POJ 2923 Relocation：狀態壓縮 DP 解決搬運問題

核心代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 12;
const int INF = 0x3f3f3f3f;
int n, m1, m2;
int a[MAXN];
bool vis[MAXN];
int dp[1 << MAXN];

// 判斷子集 x 能否一次運完
bool ok(int x) {
    int sum = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = true;
    for (int i = 0; i < n; i++) if (x & (1 << i)) {
        sum += a[i];
        for (int j = m1; j >= a[i]; j--) vis[j] |= vis[j - a[i]];
    }
    for (int i = 0; i <= m1; i++)
        if (vis[i] && sum - i <= m2) return true;
    return false;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d%d", &n, &m1, &m2);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);

        int total = 1 << n;
        fill(dp, dp + total, INF);
        dp[0] = 0;
        for (int i = 1; i < total; i++) {
            if (ok(i)) dp[i] = 1;
        }

        for (int s = 1; s < total; s++) {
            for (int sub = s; sub; sub = (sub - 1) & s) {
                if (dp[sub] == INF) continue;
                dp[s] = min(dp[s], dp[s ^ sub] + dp[sub]);
            }
        }
        printf("Scenario #%d:\n%d\n\n", cas, dp[total - 1]);
    }
    return 0;
}

複雜度分析

• 預處理：O(n × 2ⁿ × m1)，n ≤ 10，m1 ≤ 較小，可接受。
• DP 轉移：O(3ⁿ)（枚舉所有狀態及其子集），n=10 時約 59049 次，極快。

關鍵點總結

• 狀態壓縮：n ≤ 10 直接提示用位掩碼表示集合。
• 子集可行性判斷：轉化為 0-1 背包，利用布爾數組 vis 記錄可達重量。
• 子集枚舉技巧：for (int sub = s; sub; sub = (sub-1) & s) 是經典寫法，務必熟練。