HDU 1712 分組背包完整解析

有 N 組物品，每組 M 個物品，每組必須恰好選擇一個（或不選？題目通常為每組最多選一個，視具體題意）。背包容量 M，最大化價值。這是標準分組背包模型。

狀態定義

dp[j]：容量為 j 時的最大價值。

狀態轉移

對每組 i，倒序枚舉容量 j，組內枚舉物品 k：

for (int i = 0; i < n; i++) {
    for (int j = m; j >= 1; j--) {        // 倒序：01 背包特性
        for (int k = 0; k < m; k++) {     // 枚舉組內物品
            if (k + 1 <= j)               // 物品體積為 k+1（題目特定）
                dp[j] = max(dp[j], dp[j - k - 1] + c[i][k]);
        }
    }
}

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        vector> c(n, vector(m));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cin >> c[i][j];
        
        vector dp(m + 1, 0);
        
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= 1; j--) {
                for (int k = 0; k < m; k++) {
                    if (k + 1 <= j)
                        dp[j] = max(dp[j], dp[j - k - 1] + c[i][k]);
                }
            }
        }
        cout << dp[m] << '\n';
    }
    return 0;
}

關鍵點總結

• 分組背包核心：外層循環組，中層倒序容量，內層枚舉組內選項
• 倒序容量：保證同組物品互斥（每組最多選一個）
• 物品體積：本題第 k 個物品體積為 k+1（下標從 0 開始）
• 初始化：dp[0..m] = 0
• 終止條件：N=M=0 結束輸入