HDU 1171 Big Event in HDU：多重背包分割物品使兩份價值最接近

題目簡介

有 n 種設施（n ≤ 50），第 i 種價值 v_i，數量 m_i。需分成兩份，第一份總價值 ≥ 第二份，且差值最小。輸出兩份價值。

解題思路

多重背包轉換：總價值 sum = Σ v_i*m_i。目標是選取若干物品使其價值盡可能接近 sum/2 但不小於 sum/2（因第一份 ≥ 第二份）。用一維 DP 數組 dp[j] 表示能否湊出價值 j。對每種物品，用二進制優化或單調隊列優化多重背包。最後從 sum/2 向上找第一個可行的 j，輸出 j 和 sum-j。

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXV = 50*50*50 + 5; // 最大總價值 125000
int dp[MAXV];
int v[55], m[55];

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n > 0) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &v[i], &m[i]);
            sum += v[i] * m[i];
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            int cnt = m[i], val = v[i];
            for (int k = 1; cnt > 0; k <<= 1) {
                int use = min(k, cnt);
                cnt -= use;
                int w = use * val;
                for (int j = sum; j >= w; j--)
                    if (dp[j-w]) dp[j] = 1;
            }
        }
        int half = (sum + 1) / 2; // 第一份不小於第二份
        for (int j = half; j <= sum; j++)
            if (dp[j]) { printf("%d %d\n", j, sum-j); break; }
    }
    return 0;
}

複雜度分析

二進制優化後物品數 O(log m_i)，總複雜度 O(n × log m × sum)，sum ≤ 125000 可行。