HDU 1712 ACboy needs your help：分組背包問題詳解

題目大意

有 n 門課程，m 天時間。第 i 門課程花費 j 天獲得的價值為 A[i][j]。每門課程必須選擇一個天數（或 0 天），總天數不超過 m，求最大總價值。

問題建模：分組背包

• 每門課程為一「組」，組內物品為「花費 k 天、價值 A[i][k]」（k=1..m）。
• 每組必選恰好一個物品（含 0 天、0 價值的虛擬物品）。
• 背包容量為 m，求最大價值。

動態規劃轉移

dp[j]：前 i 組課程，總天數恰為 j 的最大價值。
轉移：dp[j] = max(dp[j], dp[j-k] + A[i][k])，對每組倒序枚舉 j，正序枚舉 k。

完整代碼

#include <iostream>
#include <string.h>
using namespace std;
int A[105][105];
int dp[105];

int main() {
    int n, m;
    while (cin >> n >> m && n + m) {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                cin >> A[i][j];
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j > 0; --j) {
                for (int k = 1; k <= j; ++k) {
                    dp[j] = max(dp[j], dp[j-k] + A[i][k]);
                }
            }
        }
        cout << dp[m] << endl;
    }
    return 0;
}

關鍵點解析

• 倒序 j 保證每組只選一次（0-1 背包特性）。
• 初始化 dp[0]=0，其餘 0 表示不選也合法。
• 輸入以 n+m=0 結束，注意讀取條件。

複雜度

• 時間：O(n × m²)，n,m ≤ 100，約 10^6 操作，輕鬆通過。
• 空間：O(m)。

舉一反三

分組背包變體：多重背包（每組可選多個）、依賴背包（組內有依賴關係）等，核心思想一致。