HDU 3535 AreYouBusy：混合分組背包問題

題目類型

分組背包變體：每組物品有三種限制——最多取一個、至少取一個、任意取（01背包）。求在總時間 T 內獲得的最大價值。

狀態定義與轉移

dp[i][j]：前 i 組，花費時間 j 的最大價值。初始 dp[0][0]=0，其餘 -1 表示不可達。
• 最多取一個（s=0）：同 01 背包，但只能從上一組狀態轉移。
• 至少取一個（s=1）：必須從上一組轉移並取當前組一個物品。
• 任意取（s=2）：完全背包式，可從本組已取狀態繼續取。
注意 cost 可能為 0，內層循環順序不能顛倒。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
int c[MAXN], v[MAXN], dp[MAXN][MAXN];

int main() {
    int n, T;
    while (scanf("%d%d", &n, &T) != EOF) {
        memset(dp, -1, sizeof(dp));
        for (int j = 0; j <= T; j++) dp[0][j] = 0;
        for (int i = 1; i <= n; i++) {
            int m, s; scanf("%d%d", &m, &s);
            for (int k = 1; k <= m; k++) scanf("%d%d", &c[k], &v[k]);
            if (s == 0) { // 最多取一個
                for (int k = 1; k <= m; k++)
                    for (int j = T; j >= c[k]; j--) {
                        if (dp[i][j-c[k]] != -1) dp[i][j] = max(dp[i][j], dp[i][j-c[k]] + v[k]);
                        if (dp[i-1][j-c[k]] != -1) dp[i][j] = max(dp[i][j], dp[i-1][j-c[k]] + v[k]);
                    }
            } else if (s == 1) { // 至少取一個
                for (int j = 0; j <= T; j++) dp[i][j] = dp[i-1][j];
                for (int k = 1; k <= m; k++)
                    for (int j = T; j >= c[k]; j--)
                        if (dp[i-1][j-c[k]] != -1)
                            dp[i][j] = max(dp[i][j], dp[i-1][j-c[k]] + v[k]);
            } else { // 任意取 (01背包)
                for (int j = 0; j <= T; j++) dp[i][j] = dp[i-1][j];
                for (int k = 1; k <= m; k++)
                    for (int j = T; j >= c[k]; j--)
                        if (dp[i][j-c[k]] != -1)
                            dp[i][j] = max(dp[i][j], dp[i][j-c[k]] + v[k]);
            }
        }
        int ans = 0;
        for (int j = 0; j <= T; j++) ans = max(ans, dp[n][j]);
        printf("%d\n", ans);
    }
    return 0;
}