HDU 3535 AreYouBusy：混合背包問題深度解析與動態規劃實現

題目概述

HDU 3535 "AreYouBusy" 是一道經典的混合背包問題。題目給出三種類型的任務：必須至少完成一個、至多完成一個、以及任意數量完成。現有 k 組任務，每組屬於上述三種類型之一。每個任務消耗時間並獲得幸福感，目標是在總時間 T 內最大化總幸福感。

核心思路：二維動態規劃

由於任務分組且每組有不同選擇限制，一維背包已無法滿足需求。我們定義狀態 d[k][j] 表示前 k 組任務在容量 j 時的最大幸福感。關鍵在於如何根據任務類型正確進行狀態轉移：

• 任意選擇（0/1 背包）：標準 0/1 背包轉移，只從上一組狀態轉移。
• 至少選一個：初始化時將不選的狀態標記為非法（-1），強制至少選擇一項。
• 至多選一個：在當前組已選擇的情況下不能繼續選擇，只能從上一組轉移。

狀態轉移細節

代碼中通過參數 s 區分任務類型（0: 至少一個, 1: 至多一個, 2: 任意選）。初始化時：

for(int j=0;j<=T;j++) 
    d[k][j] = (s==0 ? -1 : d[k-1][j]);

隨後對每組內的 m 個任務進行處理，根據類型採用不同的迭代順序和轉移來源，確保滿足約束條件。

完整參考代碼 (C++)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define N 110
using namespace std;

int d[N][N];

int main() {
    int n, m, s, T, c, w;
    while(~scanf("%d%d", &n, &T)) {
        memset(d, 0, sizeof(d));
        for(int k=1; k<=n; k++) {
            cin >> m >> s;
            for(int j=0; j<=T; j++) 
                d[k][j] = (s==0 ? -1 : d[k-1][j]);
            
            for(int i=0; i> c >> w;
                if(s == 0) { // 至少取一個
                    for(int j=T; j>=c; j--) {
                        if(d[k][j-c] != -1) 
                            d[k][j] = max(d[k][j], d[k][j-c] + w);
                        if(d[k-1][j-c] != -1) 
                            d[k][j] = max(d[k][j], d[k-1][j-c] + w);
                    }
                }
                if(s == 1) { // 至多取一個
                    for(int j=T; j>=c; j--) 
                        if(d[k-1][j-c] != -1) 
                            d[k][j] = max(d[k][j], d[k-1][j-c] + w);
                }
                if(s == 2) { // 任意取 (完全背包)
                    for(int j=c; j<=T; j++) {
                        if(d[k][j-c] != -1) 
                            d[k][j] = max(d[k][j], d[k][j-c] + w);
                        if(d[k-1][j-c] != -1) 
                            d[k][j] = max(d[k][j], d[k-1][j-c] + w);
                    }
                }
            }
        }
        cout << d[n][T] << endl;
    }
    return 0;
}

關鍵點總結

1. 二維 DP 數組 d[組數][容量] 記錄分組決策狀態。
2. 用 -1 標記非法狀態，巧妙處理「至少選一」的約束。
3. 三種背包類型通過迭代方向和轉移來源區分：逆序+雙來源(至少一)、逆序+單來源(至多一)、正序+雙來源(任意選)。
4. 時間複雜度 O(n * m * T)，空間可優化至一維但二維更直觀。

此題是混合背包問題的優秀範例，掌握其狀態定義與轉移邏輯，對解決各類分組約束背包問題極有幫助。