POJ 1014 Dividing 多重背包經典：大理石平分問題的三種解法對比

問題描述

有 6 種價值為 1~6 的大理石，給定每種數量，判斷能否平分為兩堆價值相等。多組測試，全 0 結束。

核心思路

總價值 sum 若為奇數直接不可分。偶數時目標容量 V = sum/2，轉化為多重背包可行性問題：能否恰好裝滿容量 V。

解法一：二進制拆分 + 01 背包 (dp 價值數組)

#include <stdio.h>
#include <string.h>

int sum, c[12], dp[120002];

void zero_one(int w, int v) {
    for (int j = sum; j >= w; j--)
        dp[j] = max(dp[j], dp[j - w] + v);
}

int main() {
    int count = 0;
    while (1) {
        sum = 0;
        for (int i = 1; i <= 6; i++) {
            scanf("%d", &c[i]);
            sum += i * c[i];
        }
        if (!sum) break;
        
        printf("Collection #%d:\n", ++count);
        if (sum % 2) {
            puts("Can't be divided.\n");
            continue;
        }
        
        sum /= 2;
        memset(dp, 0, sizeof(dp));
        
        for (int i = 1; i <= 6; i++) {
            if (i * c[i] > sum) {  // 完全背包
                for (int j = i; j <= sum; j++)
                    dp[j] = max(dp[j], dp[j - i] + i);
            } else {  // 二進制拆分
                int k = 1;
                while (k < c[i]) {
                    zero_one(k * i, k * i);
                    c[i] -= k;
                    k *= 2;
                }
                zero_one(c[i] * i, c[i] * i);
            }
        }
        
        puts(dp[sum] == sum ? "Can be divided.\n" : "Can't be divided.\n");
    }
    return 0;
}

解法二：優化的多重背包 O(6V) - f/used 數組法

利用物品種類固定為 6 種的特點，直接用 f[j] 表示容量 j 是否可達，used[j] 記錄當前物品使用數。

int sum, c[12], f[120002], used[120002];

int main() {
    // ... 讀入與奇數判斷同前 ...
    sum /= 2;
    memset(f, 0, sizeof(f));
    f[0] = 1;
    
    for (int i = 1; i <= 6; i++) {
        memset(used, 0, sizeof(used));
        for (int j = i; j <= sum; j++) {
            if (!f[j] && f[j - i] && used[j - i] < c[i]) {
                f[j] = 1;
                used[j] = used[j - i] + 1;
            }
        }
        if (f[sum]) break;  // 提前剪枝
    }
    puts(f[sum] ? "Can be divided.\n" : "Can't be divided.\n");
}

解法三：位運算優化

由於物品價值等於重量，且種類極少(6)，可用 bitset 或手動位運算進一步加速，此處不贅述。

三種解法對比

關鍵技巧總結

1. 完全背包判斷：單種物品總價值 > 目標容量時退化為完全背包
2. 提前剪枝：任一物品處理後 f[sum]==1 即可直接判定可分
3. 數組大小：最大總價值 6×10000=60000，半為 30000，開 120000+ 安全
4. 輸出格式：嚴格遵循題目要求的空行與大小寫