您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 1171 大事件：多重背包與母函數雙重解法詳解

編輯：C++ 入門

HDU 1171 Big Event in HDU

HDU 1171「Big Event in HDU」是一道經典的多重背包問題，題目要求將 N 種設施（每種有價值 V 和數量 M）分成兩堆，使兩堆價值差最小，且第一堆價值不小於第二堆。本文提供兩種解法：多重背包優化與母函數法。

問題描述

給定 N 種設施（N ≤ 50），每種有價值 V（V ≤ 50）和數量 M（M ≤ 100），所有 V 不同。需將設施分為兩組 A 和 B，使 A ≥ B 且 A - B 最小。輸出 A 和 B 的值。

解法一：多重背包優化（二進制拆分/完全背包轉換）

核心思路：總價值 sum = Σ(V_i × M_i)，目標是找到不超過 sum/2 的最大可達成價值。對於每種物品，若 V_i × M_i ≥ sum/2，視為完全背包；否則用 01 背包多重處理。

代碼實現

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int dp[100000], sum, ans;
struct Item { int v, m; } data[100000];

void completePack(int x) {
    for(int i = data[x].v; i <= ans; i++)
        dp[i] = max(dp[i], dp[i - data[x].v] + data[x].v);
}

void zeroOnePack(int x) {
    for(int j = 1; j <= data[x].m; j++)
        for(int i = ans; i >= data[x].v; i--)
            dp[i] = max(dp[i], dp[i - data[x].v] + data[x].v);
}

int main() {
    int n;
    while(scanf("%d", &n) && n > 0) {
        memset(dp, 0, sizeof(dp));
        sum = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &data[i].v, &data[i].m);
            sum += data[i].v * data[i].m;
        }
        ans = sum / 2;
        for(int i = 1; i <= n; i++) {
            if(data[i].v * data[i].m >= ans) completePack(i);
            else zeroOnePack(i);
        }
        printf("%d %d\n", sum - dp[ans], dp[ans]);
    }
    return 0;
}

解法二：母函數法

母函數利用多項式乘法的係數來表示可達成的價值組合。初始化 s[0] = 1，對每種物品，將其價值作為步長進行多項式乘法，最終從 sum/2 向下尋找第一個係數非零的位置。

代碼實現

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

int a[250010], s[250010];
int v[55], m[55];

int main() {
    int n, i, j, k, sum, ans;
    while(scanf("%d", &n) && n > 0) {
        sum = 0;
        memset(s, 0, sizeof(s));
        memset(a, 0, sizeof(a));
        for(i = 1; i <= n; i++) {
            scanf("%d%d", &v[i], &m[i]);
            sum += v[i] * m[i];
        }
        for(i = 0; i <= v[1] * m[1]; i += v[1])
            s[i] = 1;
        for(i = 2; i <= n; i++) {
            for(j = 0; j <= sum; j++) {
                for(k = 0; k + j <= sum && k <= v[i] * m[i]; k += v[i])
                    a[k + j] += s[j];
            }
            for(k = 0; k <= sum; k++) {
                s[k] = a[k];
                a[k] = 0;
            }
        }
        for(i = sum / 2; i >= 0; i--) {
            if(s[i]) {
                printf("%d %d\n", sum - i, i);
                break;
            }
        }
    }
    return 0;
}