POJ 1948：二維背包求最大三角形面積完整解析

POJ 1948 給定 n (≤40) 根木棒，長度 ≤40，選擇若干根組成三角形，求最大面積。每根木棒只能用一次，不可切割。

核心觀察

1. 三角形三邊 a, b, c 滿足：a+b>c, a+c>b, b+c>a（等價於任意兩邊之和大於第三邊）
2. 周長 P = a+b+c 固定為所選木棒總長度
3. 海倫公式：S = √[p(p-a)(p-b)(p-c)]，p = P/2
4. 若 a,b 確定，則 c = P - a - b

動態規劃狀態設計

dp[i][j]：是否能用部分木棒組成兩堆，長度分別為 i 和 j（第三堆隱含為 sum - i - j）。

• 狀態空間：i, j ≤ 800（最大周長 40×40=1600，半周長 800）
• 滾動陣列優化：只需 dp[801][801]，反向迴圈避免重複使用同一根木棒

狀態轉移

對於每根長度為 L 的木棒：
for i from 800 down to 0:
    for j from i down to 0:  // 利用對稱性 j ≤ i
        if i >= L and dp[i-L][j]   dp[i][j] = true; // 放入第一堆
        if j >= L and dp[i][j-L]   dp[i][j] = true; // 放入第二堆

答案計算

double ans = 0;
for i = 0..800:
    for j = 0..i:
        if dp[i][j]:
            k = sum - i - j;
            if (i+j>k && i+k>j && j+k>i) { // 三角形不等式
                double p = (i+j+k)/2.0;
                double area = sqrt(p*(p-i)*(p-j)*(p-k));
                ans = max(ans, area);
            }

完整 AC 代碼

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

bool dp[801][801];
int sticks[45];

double area(int a, int b, int c) {
    double p = (a + b + c) / 2.0;
    return sqrt(p * (p-a) * (p-b) * (p-c));
}

bool valid(int a, int b, int c) {
    return a+b>c && a+c>b && b+c>a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while (cin >> n) {
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            cin >> sticks[i];
            sum += sticks[i];
        }
        
        memset(dp, 0, sizeof(dp));
        dp[0][0] = true;
        
        for (int idx = 0; idx < n; ++idx) {
            int L = sticks[idx];
            for (int i = 800; i >= 0; --i) {
                for (int j = i; j >= 0; --j) { // j <= i 利用對稱性
                    if (i >= L && dp[i-L][j]) dp[i][j] = true;
                    if (j >= L && dp[i][j-L]) dp[i][j] = true;
                }
            }
        }
        
        double ans = 0;
        for (int i = 0; i <= 800; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (dp[i][j]) {
                    int k = sum - i - j;
                    if (k < 0) continue;
                    if (valid(i, j, k)) {
                        ans = max(ans, area(i, j, k));
                    }
                }
            }
        }
        
        if (ans == 0) cout << "-1\n";
        else cout << int(ans * 1000) / 10.0 << '\n'; // 保留一位小數
    }
    return 0;
}

關鍵優化技巧

1. 對稱性剪枝：只枚舉 j ≤ i，狀態數減半
2. 反向迴圈：0-1 背包必須反向，避免同一物品重複使用
3. 周長上界：最大周長 1600，半周長 800，狀態空間固定
4. 輸出格式：題目要求保留一位小數，int(ans*1000)/10.0 避免浮點誤差

複雜度分析

• 時間：O(n × 800²) ≈ 40 × 640,000 = 25.6M 操作，極快
• 空間：O(800²) ≈ 640KB boolean 陣列

延伸思考

• 若木棒數量大幅增加（如 1000 根），需改用 bitset 優化或贪心+搜索
• 若要求輸出具體構成，需記錄決策路徑
• 最大面積三角形在周長固定時接近等邊三角形，可作為啟發式剪枝依據

此題完美展示了「二維背包 + 幾何性質 + 狀態壓縮」的綜合應用，是背包問題進階的經典範例。