POJ 2576 Tug of War：拔河比賽的動態規劃解法

問題描述

有 n 人參加拔河比賽，每人體重 w[i]。需分成兩隊，人數差 ≤ 1，使兩隊總重量差最小。輸出較輕隊與較重隊的重量。

狀態定義與轉移

初始想法 dp[i][j] 表示前 i 人能否湊出重量 j，但需記錄路徑（選了哪些人）導致狀態爆炸。
關鍵洞察：只需知道「湊出重量 j 時選了多少人」，無需具體路徑。
定義三維狀態：dp[k][j] 表示選 k 人能否湊出重量 j（省略 i 維，逆序迭代保證 0-1 背包特性）。

狀態轉移方程

for (int i = 1; i <= n; ++i) {
    for (int j = sum; j >= w[i]; --j) {
        for (int k = n/2 + 1; k >= 1; --k) {
            if (dp[k-1][j - w[i]]) dp[k][j] = true;
        }
    }
}

答案提取

總重量 sum。從 sum/2 向下枚舉 j，找第一個可行的分配：

• 若 n 為偶數：需 dp[n/2][j] 為真。
• 若 n 為奇數：dp[n/2][j] 或 dp[n/2+1][j] 為真均可（兩隊人數差 1）。

輸出 j 和 sum - j（j ≤ sum - j）。

完整代碼

#include <cstdio>
#include <cstring>

const int MAXN = 105;
const int MAXW = 45005;
int dp[MAXN][MAXW];
int w[MAXN];
int n;

void init() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
}

int main() {
    scanf("%d", &n);
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &w[i]);
        sum += w[i];
    }
    init();

    for (int i = 1; i <= n; ++i) {
        for (int j = sum; j >= w[i]; --j) {
            for (int k = n/2 + 1; k >= 1; --k) {
                if (dp[k-1][j - w[i]]) dp[k][j] = 1;
            }
        }
    }

    for (int j = sum/2; j >= 0; --j) {
        if (n & 1) { // 奇數
            if (dp[n/2][j] || dp[n/2+1][j]) {
                printf("%d %d\n", j, sum - j);
                break;
            }
        } else { // 偶數
            if (dp[n/2][j]) {
                printf("%d %d\n", j, sum - j);
                break;
            }
        }
    }
    return 0;
}

複雜度分析

• 時間：O(n * sum * n) ≈ O(n² * sum)，n ≤ 100，sum ≤ 45000，約 4.5×10⁸ 操作，邊界較緊，但實測通過（可優化 k 循環上界為 i）。
• 空間：O(n * sum) ≈ 4.5M bool，約 4.5 MB。

核心心得

「不需要知道具體選了誰，只需要知道選了多少人」—— 這一狀態降維的思想，將看似需要路徑記錄的問題轉化為純可行性 DP，是背包類問題中極具啟發性的技巧。