POJ 1014 / HDU 1059 Dividing：多重背包判斷能否等分

問題描述

有價值 1~6 的寶物各 num[i] 個。問能否分成價值相等的兩堆。多測試案例，全 0 結束。

轉化為 01 背包可行性

總價值 sum = Σ i·num[i]。若 sum 為奇數 → 不可能。
目標：能否選出若干寶物，總價值恰為 sum/2。
這是多重背包可行性問題：物品價值 = 重量 = i，數量 = num[i]，容量 = V = sum/2。

二進制優化多重背包

將數量 n 拆分為 1, 2, 4, ..., 2ᵏ, 餘數，轉化為 O(log n) 個 01 物品。
對每個拆分項 cnt，調用 01 背包：for (i=V; i>=cnt*w; --i) dp[i] = max(dp[i], dp[i-cnt*w] + cnt*v)。
若 cnt*w ≥ V，視為完全背包處理（for (i=cnt*w; i<=V; ++i)）。

程式碼實現（C++）

/* POJ 1014 / HDU 1059 Dividing - Binary Optimized Multiple Knapsack */
#include <bits/stdc++.h>
using namespace std;

int dp[120005], num[7];
int V;

void zeroOnePack(int cost, int weight) {
    for (int i = V; i >= cost; --i) dp[i] = max(dp[i], dp[i-cost] + weight);
}
void completePack(int cost, int weight) {
    for (int i = cost; i <= V; ++i) dp[i] = max(dp[i], dp[i-cost] + weight);
}
void multiplePack(int cost, int weight, int amount) {
    if (cost * amount >= V) { completePack(cost, weight); return; }
    int k = 1;
    while (k < amount) {
        zeroOnePack(cost * k, weight * k);
        amount -= k; k <<= 1;
    }
    zeroOnePack(cost * amount, weight * amount);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cas = 1;
    while (true) {
        int sum = 0;
        for (int i = 1; i <= 6; ++i) { cin >> num[i]; sum += num[i] * i; }
        if (sum == 0) break;
        cout << "Collection #" << cas++ << ":\n";
        if (sum & 1) { cout << "Can't be divided.\n\n"; continue; }
        V = sum / 2;
        fill(dp, dp + V + 1, 0);
        for (int i = 1; i <= 6; ++i)
            if (num[i]) multiplePack(i, i, num[i]);
        if (dp[V] == V) cout << "Can be divided.\n\n";
        else cout << "Can't be divided.\n\n";
    }
    return 0;
}

關鍵點

• 價值=重量：簡化為單維度背包。
• 二進制拆分：將多重背包高效轉化為 01 背包，避免 O(V·Σnum) 暴力。
• 完全背包優化：當單類物品總重 ≥ 容量時，退化為完全背包（正序循環）。
• 輸出格式：注意空行與大小寫。

複雜度

• 每案例：O(6 · V · log max_num)，V ≤ 60000，極快。

總結

POJ 1014 是多重背包二進制優化的標準模板題。核心模板 multiplePack 處理三種情況（01、完全、二進制拆分）是背包問題必備工具。題目本身簡單，但強化了「可行性背包」與「二進制拆分」兩大核心技能。