HDU 3535 AreYouBusy：混合背包（三類組約束）完整解析

HDU 3535 是高難度混合背包：n 堆工作，每堆有 num[i] 個子任務，三種約束類型：

• Type 0：至少做 1 個
• Type 1：最多做 1 個
• Type 2：任意選（0-1 背包）

總時間 ≤ t，最大化幸福感。若無可行解輸出 -1。

統一建模：每堆為一組

用二維 DP：dp[i][j] = 前 i 組花費 j 時間的最大幸福感（-1 不可達）

三類型的轉移邏輯

Type 0：至少做一個（分組背包變體）

同 HDU 3033：首項從 dp[i-1]，後續從 dp[i]

for each task in group i:
    for j = m..cost:
        if (dp[i][j-cost] != -1)   dp[i][j] = max(dp[i][j], dp[i][j-cost] + val);
        if (dp[i-1][j-cost] != -1) dp[i][j] = max(dp[i][j], dp[i-1][j-cost] + val);

Type 1：最多做一個（標準分組背包）

僅從 dp[i-1] 轉移，組內任務互斥

for j = m..0:
    for each task in group i:
        if (j >= cost && dp[i-1][j-cost] != -1)
            dp[i][j] = max(dp[i][j], dp[i-1][j-cost] + val);
// 別忘了複製「不選」狀態
for j = 0..m: dp[i][j] = max(dp[i][j], dp[i-1][j]);

Type 2：任意選（0-1 背包）

從 dp[i] 和 dp[i-1] 都可轉移，並複製「不選」

for each task in group i:
    for j = m..cost:
        if (dp[i][j-cost] != -1)   dp[i][j] = max(dp[i][j], dp[i][j-cost] + val);
        if (dp[i-1][j-cost] != -1) dp[i][j] = max(dp[i][j], dp[i-1][j-cost] + val);
for j = 0..m: dp[i][j] = max(dp[i][j], dp[i-1][j]);

完整 AC 代碼

#include 
#include 
#define MAX 102
#define MAXV(a,b) ((a)>(b)?(a):(b))

int n, m;
int num[MAX], type[MAX];
int cost[MAX][MAX], val[MAX][MAX];
int dp[MAX][MAX];

int solve() {
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        if (type[i] == 0) {                    // 至少一個
            for (int k = 1; k <= num[i]; k++) {
                int c = cost[i][k], v = val[i][k];
                for (int j = m; j >= c; j--) {
                    if (dp[i][j-c] != -1)   dp[i][j] = MAXV(dp[i][j], dp[i][j-c] + v);
                    if (dp[i-1][j-c] != -1) dp[i][j] = MAXV(dp[i][j], dp[i-1][j-c] + v);
                }
            }
        } else if (type[i] == 1) {             // 最多一個
            for (int j = m; j >= 0; j--)
                for (int k = 1; k <= num[i]; k++) {
                    int c = cost[i][k], v = val[i][k];
                    if (j >= c && dp[i-1][j-c] != -1)
                        dp[i][j] = MAXV(dp[i][j], dp[i-1][j-c] + v);
                }
            for (int j = 0; j <= m; j++)       // 複製不選
                dp[i][j] = MAXV(dp[i][j], dp[i-1][j]);
        } else {                                // 任意選 (Type 2)
            for (int k = 1; k <= num[i]; k++) {
                int c = cost[i][k], v = val[i][k];
                for (int j = m; j >= c; j--) {
                    if (dp[i][j-c] != -1)   dp[i][j] = MAXV(dp[i][j], dp[i][j-c] + v);
                    if (dp[i-1][j-c] != -1) dp[i][j] = MAXV(dp[i][j], dp[i-1][j-c] + v);
                }
            }
            for (int j = 0; j <= m; j++)       // 複製不選
                dp[i][j] = MAXV(dp[i][j], dp[i-1][j]);
        }

        // 檢查本組是否有可行狀態
        bool ok = false;
        for (int j = 0; j <= m; j++) if (dp[i][j] != -1) { ok = true; break; }
        if (!ok) return -1;
    }

    int ans = -1;
    for (int j = 0; j <= m; j++) ans = MAXV(ans, dp[n][j]);
    return ans;
}

int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &num[i], &type[i]);
            for (int j = 1; j <= num[i]; j++)
                scanf("%d %d", &cost[i][j], &val[i][j]);
        }
        printf("%d\n", solve());
    }
    return 0;
}

關鍵細節總結

測試樣例

Input:
1 0
2 0
0 1
0 2

Output:
-1  // 容量 0，Type 0 至少做一個但任務需時 2，不可行

三類型統一視角

所有類型本質上都是在回答：「本組的狀態從哪些前驅狀態轉移而來？」

• Type 0：首項必須來自上組（強制選一），後續可來自本組
• Type 1：所有項目均來自上組（互斥），並保留上組狀態（可不選）
• Type 2：所有項目可來自上組或本組（獨立 0-1），並保留上組狀態

結語

HDU 3535 將三種背包約束融合在一個 DP 框架中，是混合背包的經典教學案例。解題關鍵：按組處理、二維 DP 保留歷史、根據類型選擇正確的轉移來源、不要忘記「不選」的狀態繼承。遇到新約束類型時，只需分析其「合法選擇集合」對應的前驅狀態，即可寫出正確轉移。